Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/net-admin/problem?isFullScreen=true
In this HackerRank in Data Structures -
Like every IT company, the Uplink Corporation has its own network. But, unlike the rest of the companies around the world, Uplink's network is subject to very specific restrictions:
- Any pair of servers within the network should be directly connected by at most 1 link.
- Each link is controlled by some specific network administrator.
- No server has more than 2 links connected to it, that are controlled by the same administrator.
- For easier management, links controlled by some administrator cannot be redundant (this is, removing any link will disconnect some two previously connected servers)
Notice that 2 connected servers might not have any direct link between them. Furthermore, in order to keep the network in a secured status, Uplink directives periodically try to perform some modifications over the network to mislead hackers. The problem is, having such a huge network, they need a software to efficiently simulate the network status after any of such modifications. You have been assigned to write the core section of that software.
Operations performed by the directives are:
- Change the administrator assigned to some particular link.
- Place some number of security devices along a particular link.
Also, given a network administrator, they would like to know how many devices are in the path created by links controlled by that administrator (if any) between 2 servers.
Input Format
Input begins with a line containing 4 integers S,L,A,T separated by a single whitespace, denoting the number of servers, links, network administrators and transformations, respectively. L lines follow each one with 3 integers x,y (x < y) and ai (1 <= ai <= A), saying that there is a link between server x and server y and that link is controlled by administrator ai . Initially, network topology fulfills the restrictions described above and there is no security device along any link. Remaining T lines in the input follow one the next formats:
- 1 AB ai
meaning that link between server A and server B (A < B) is requested to be assigned to administrator ai.
- 2 A B x
meaning that the number of security devices along the link between server A and server B (A < B) will be fixed to x, removing any existing devices on this link before the operation. The involved link will always exist.
- 3 A B ai
meaning that directives want to know the number of security devices placed along the path between server A and server B, just considering links controlled by administrator ai
Output Format
For each network transformation in the form 1 A Bai ou should output:
- "Wrong link" if there is no direct link between server A and server B.
- Already controlled link" if the requested link does exist, but it is already controlled by administrator ai .
- "Server overload" if administrator ai already controls 2 links connected to one of the involved servers.
- "Network redundancy" if the requested assignment creates no new connection considering just the links controlled by ai .
- "Assignment done" if none of the above conditions holds. In this case, link directly connecting A with B is assigned to ai .
For each network transformation in the form 2 A Bai you should output:
- "No connection" if there is no path between the requested servers considering just the links controlled by ai .
- "D security devices placed" where D is the number of security devices placed so far on the existing connection between the requested servers considering just the links controlled by ai .
Constraints
1 <= S <= 105
1 <= L <= 5 * 105
1 <= A <= 102
1 <= T <= 5 * 105
1 <= x <= 2000
Sample Input:
4 5 3 15
1 2 1
2 3 1
3 4 2
1 4 2
1 3 3
2 3 4 49
1 1 2 3
2 1 4 64
3 1 4 2
1 1 2 3
3 4 2 3
3 1 3 3
1 1 4 3
3 3 4 2
3 2 4 1
2 1 4 13
2 1 3 21
2 2 3 24
1 2 3 3
1 2 4 3
Sample Output:
Assignment done
64 security devices placed
Already controlled link
No connection
0 security devices placed
Server overload
49 security devices placed
No connection
Network redundancy
Wrong link
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _ct_node{
int x;
int y;
int size;
int priority;
int a;
int value;
int sum;
int reverse;
struct _ct_node *left,*right,*parent,*next;
} ct_node;
int sum_link(int x,int y,int z);
void change_link(ct_node *p,int x);
int insert_link(ct_node *p,int x);
void remove_link(ct_node *p);
void find(ct_node *p,int *idx,ct_node **ret);
void insert(ct_node *p);
ct_node* search(int x,int y);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
int sumOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
int sum(ct_node *p,int x,int y);
void push(ct_node *root);
ct_node *a[100000][100][2],*hash[HASH_SIZE];
int main(){
int S,L,A,T,x,y,z,w,i;
ct_node *p;
scanf("%d%d%d%d",&S,&L,&A,&T);
for(i=0;i < L;i++){
scanf("%d%d%d",&x,&y,&z);
x--;
y--;
z--;
p=(ct_node*)malloc(sizeof(ct_node));
p->x=x;
p->y=y;
p->size=1;
p->priority=rand();
p->a=z;
p->value=p->sum=p->reverse=0;
p->left=p->right=p->parent=p->next=NULL;
insert(p);
insert_link(p,z);
}
while(T--){
scanf("%d%d%d%d",&w,&x,&y,&z);
if(w==1){
p=search(x-1,y-1);
if(!p)
p=search(y-1,x-1);
if(!p)
printf("Wrong link\n");
else if(p->a==z-1)
printf("Already controlled link\n");
else if(a[x-1][z-1][1] || a[y-1][z-1][1])
printf("Server overload\n");
else{
w=p->a;
remove_link(p);
if(insert_link(p,z-1)){
insert_link(p,w);
printf("Network redundancy\n");
}
else
printf("Assignment done\n");
}
}
else if(w==2){
p=search(x-1,y-1);
if(p)
change_link(p,z);
else
change_link(search(y-1,x-1),z);
}
else{
if(x==y){
printf("No connection\n");
continue;
}
w=sum_link(x-1,y-1,z-1);
if(w==-1)
printf("No connection\n");
else
printf("%d security devices placed\n",w);
}
}
return 0;
}
int sum_link(int x,int y,int z){
int ret,idx1,idx2,idx3,idx4;
ct_node *p1,*p2,*p3,*p4,*pp1,*pp2;
p1=a[x][z][0];
p2=a[x][z][1];
p3=a[y][z][0];
p4=a[y][z][1];
if(!p1 || !p3)
return -1;
find(p1,&idx1,&pp1);
find(p3,&idx3,&pp2);
idx2=idx4=-1;
if(p2)
find(p2,&idx2,&pp1);
if(p4)
find(p4,&idx4,&pp2);
/////////////////////
if(idx2!=-1 && !(idx1-idx2==1 || idx2-idx1==1)){
while(1);
printf("Oh no. %d %d\n",idx1,idx2);
}
if(idx4!=-1 && !(idx3-idx4==1 || idx4-idx3==1)){
while(1);
printf("Oh no. %d %d\n",idx3,idx4);
}
/////////////////////
if(pp1!=pp2)
return -1;
if(idx2==-1 && idx4==-1)
return pp1->sum;
if(idx1==idx3)
return sum(pp1,idx1,idx3);
else if(idx1<idx3)
if(idx2==-1)
if(idx3 < idx4)
return sum(pp1,idx1,idx3);
else
return sum(pp1,idx1,idx4);
else if(idx4==-1)
if(idx1 < idx2)
return sum(pp1,idx2,idx3);
else
return sum(pp1,idx1,idx3);
else
if(idx1 < idx2)
if(idx3{
p->value=x;
recalc(p);
for(;p->parent;p=p->parent)
recalc(p->parent);
return;
}
int insert_link(ct_node *p,int x){
int idx1,idx2;
ct_node *p1,*p2;
p->a=x;
if(!a[p->x][x][0] && !a[p->y][x][0]){
a[p->x][x][0]=p;
a[p->y][x][0]=p;
return 0;
}
else if(!a[p->x][x][0] && a[p->y][x][0]){
find(a[p->y][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][0]=p;
a[p->y][x][1]=p;
return 0;
}
else if(a[p->x][x][0] && !a[p->y][x][0]){
find(a[p->x][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][1]=p;
a[p->y][x][0]=p;
return 0;
}
find(a[p->x][x][0],&idx1,&p1);
find(a[p->y][x][0],&idx2,&p2);
if(p1==p2)
return 1;
if(!idx1 && !idx2){
p1->reverse^=1;
merge(p1,merge(p,p2));
}
else if(!idx1 && idx2)
merge(p2,merge(p,p1));
else if(idx1 && !idx2)
merge(p1,merge(p,p2));
else{
p2->reverse^=1;
merge(p1,merge(p,p2));
}
a[p->x][x][1]=p;
a[p->y][x][1]=p;
return 0;
}
void remove_link(ct_node *p){
int idx;
ct_node *p1,*p2;
find(p,&idx,&p1);
split(idx-1,&p1,&p2,p1);
split(0,&p1,&p2,p2);
if(a[p->x][p->a][0]==p)
a[p->x][p->a][0]=a[p->x][p->a][1];
if(a[p->y][p->a][0]==p)
a[p->y][p->a][0]=a[p->y][p->a][1];
a[p->x][p->a][1]=NULL;
a[p->y][p->a][1]=NULL;
return;
}
void find(ct_node *p,int *idx,ct_node **ret){
int d,i;
for(i=-1;p->parent;p=p->parent){
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
if(p->parent->left==p)
d=0;
else
d=1;
}
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
*idx=i;
*ret=p;
return;
}
void insert(ct_node *p){
int bucket=(p->x+100000LL*p->y)%HASH_SIZE;
p->next=hash[bucket];
hash[bucket]=p;
return;
}
ct_node* search(int x,int y){
int bucket=(x+100000LL*y)%HASH_SIZE;
ct_node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return t;
t=t->next;
}
return NULL;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
if(L->right)
L->right->parent=NULL;
L->right=merge(L->right,R);
if(L->right)
L->right->parent=L;
recalc(L);
return L;
}
push(R);
if(R->left)
R->left->parent=NULL;
R->left=merge(L,R->left);
if(R->left)
R->left->parent=R;
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
int sumOf(ct_node *root){
return (root)?root->sum:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
root->sum=sumOf(root->left)+sumOf(root->right)+root->value;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x>{
if(root->right)
root->right->parent=NULL;
split(x-curIndex-1,&t,R,root->right);
if(t)
t->parent=root;
root->right=t;
recalc(root);
*L=root;
}
else{
if(root->left)
root->left->parent=NULL;
split(x,L,&t,root->left);
if(t)
t->parent=root;
root->left=t;
recalc(root);
*R=root;
}
return;
}
int sum(ct_node *p,int x,int y){
int ret;
ct_node *p1,*p2;
split(y,&p2,&p,p);
split(x-1,&p1,&p2,p2);
ret=p2->sum;
merge(p1,merge(p2,p));
return ret;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef pair < int, int> PII;
struct Edge : PII {
Edge(int a = 0, int b = 0, int i = 0, int l = 0){
first = a; second = b; k = i; len = l;
}
int k, len;
} edge[500010];
struct Node {
Node *fa, *ch[2];
int sum, arc[2];
bool rev;
void init(){
fa = ch[0] = ch[1] = 0;
rev = false;
}
int get_sum() const {
return this ? sum : 0;
}
int get_arc(int c) const {
return ch[c] ? edge[arc[c]].len : 0;
}
void mark_rev(){
if(this == 0) return;
rev = !rev;
swap(ch[0], ch[1]);
swap(arc[0], arc[1]);
}
void push_down(){
if(rev){
rev = false;
ch[0]->mark_rev();
ch[1]->mark_rev();
}
}
void update(){
sum = ch[0]->get_sum() + get_arc(0)
+ ch[1]->get_sum() + get_arc(1);
}
void rotate(int c){
Node *y = fa;
y->ch[1 - c] = ch[c];
if(ch[c])
ch[c]->fa = y;
fa = y->fa;
if(y->fa != 0){
if(y->fa->ch[0] == y)
y->fa->ch[0] = this;
else
y->fa->ch[1] = this;
}
ch[c] = y;
y->fa = this;
y->update();
}
void splay(Node *f){
push_down();
while(fa != f){
if(fa->fa == f){
fa->push_down(); push_down();
if(fa->ch[0] == this)
rotate(1);
else
rotate(0);
} else{
Node *y = fa, *z = y->fa;
z->push_down(); y->push_down(); push_down();
if(z->ch[0] == y){
if(y->ch[0] == this)
y->rotate(1), rotate(1);
else
rotate(0), rotate(1);
} else{
if(y->ch[1] == this)
y->rotate(0), rotate(0);
else
rotate(1), rotate(0);
}
}
}
update();
}
} nodes[1000010], *ptr = nodes;
struct Administrator {
int degree[100010];
Node* mem[100010];
Node* node(int v){
return mem[v] ? mem[v] : (mem[v] = ptr++);
}
bool link(int v, int u, int p){
node(v)->splay(0); node(u)->splay(0);
if(node(v)->fa == 0 && node(u)->fa == 0){
if(node(v)->ch[1]){
node(v)->mark_rev();
node(v)->push_down();
}
if(node(u)->ch[0]){
node(u)->mark_rev();
node(u)->push_down();
}
node(v)->ch[1] = node(u);
node(v)->arc[1] = p;
node(u)->fa = node(v);
node(u)->arc[0] = p;
node(v)->update();
++degree[v], ++degree[u];
return true;
} else{
return false;
}
}
void cut(int v, int u){
node(v)->splay(0); node(u)->splay(node(v));
if(node(v)->ch[0] == node(u)){
node(v)->ch[0] = 0;
} else{
node(v)->ch[1] = 0;
}
node(v)->update();
node(u)->fa = 0;
--degree[v]; --degree[u];
}
int query(int v, int u){
node(u)->splay(0); node(v)->splay(0);
if(node(v)->fa == 0 && node(u)->fa == 0)
return -1;
node(u)->splay(node(v));
if(node(v)->ch[0] == node(u))
return node(v)->get_arc(0) + node(u)->ch[1]->get_sum()
+ node(u)->get_arc(1);
else
return node(u)->get_arc(0) + node(u)->ch[0]->get_sum()
+ node(v)->get_arc(1);
}
void modify(int v, int u){
node(v)->splay(0); node(u)->splay(0);
}
} admin[101];
int main(){
int S, L, A, T;
scanf("%d%d%d%d", &S, &L, &A, &T);
for(int i = 0; i < L; ++i){
int a, b, k;
scanf("%d%d%d", &a, &b, &k>;
if(a > b) swap(a, b);
edge[i] = Edge(a, b, k);
}
sort(edge, edge + L);
for(int i = 0; i < L; ++i)
admin[edge[i].k].link(edge[i].first, edge[i].second, i);
for(int i = 0; i < T; ++i){
int opt; scanf("%d", &opt);
if(opt == 1){
int a, b, k;
scanf("%d%d%d", &a, &b, &k>;
if(a > b) swap(a, b);
int p = lower_bound(edge, edge + L, PII(a, b)) - edge;
if(p == L || edge[p] != PII(a, b)){
puts("Wrong link");
} else if(edge[p].k == k){
puts("Already controlled link");
} else if(admin[k].degree[a] == 2 || admin[k].degree[b] == 2){
puts("Server overload");
} else if(!admin[k].link(a, b, p)){
puts("Network redundancy");
} else{
admin[edge[p].k].cut(a, b);
edge[p].k = k;
puts("Assignment done");
}
} else if(opt == 2){
int a, b, x;
scanf("%d%d%d", &a, &b, &x);
if(a > b) swap(a, b);
int p = lower_bound(edge, edge + L, PII(a, b)) - edge;
edge[p].len = x;
admin[edge[p].k].modify(a, b);
} else{
int a, b, k;
scanf("%d%d%d", &a, &b, &k);
int r = admin[k].query(a, b);
if(r == -1){
puts("No connection");
} else{
printf("%d security devices placed\n", r);
}
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class Network_administration {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
NetworkAdministration solver = new NetworkAdministration();
solver.solve(1, in, out);
out.close();
}
}
class NetworkAdministration {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int S = in.nextInt();
int L = in.nextInt();
int A = in.nextInt();
int T = in.nextInt();
LinkCutTree.Node[][] lct = new LinkCutTree.Node[A][S];
byte[][] deg = new byte[A][S];
Info[] infos = new Info[L];
for (int i = 0; i < L; i++) {
int x = in.nextInt() - 1;
int y = in.nextInt() - 1;
int a = in.nextInt() - 1;
LinkCutTree.Node edgeNode = new LinkCutTree.Node(0);
if (lct[a][x] == null) {
lct[a][x] = new LinkCutTree.Node(0);
}
if (lct[a][y] == null) {
lct[a][y] = new LinkCutTree.Node(0);
}
LinkCutTree.link(lct[a][x], edgeNode);
LinkCutTree.link(lct[a][y], edgeNode);
++deg[a][x];
++deg[a][y];
infos[i] = new Info(a, edgeNode, edge(x, y));
}
Arrays.sort(infos, new Comparator < Info>() {
public int compare(Info a, Info b) {
return Long.compare(a.edge, b.edge);
}
});
long[] edges = new long[L];
for (int i = 0; i < L; i++) {
edges[i] = infos[i].edge;
}
for (int i = 0; i < T; i++) {
int t = in.nextInt();
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
if (t == 1) {
int admin = in.nextInt() - 1;
long e = edge(a, b);
int index = Arrays.binarySearch(edges, e);
Info info = index < 0 ? null : infos[index];
Integer prevAdmin = info == null ? null : info.admin;
if (prevAdmin == null) {
out.println("Wrong link");
} else if (prevAdmin == admin) {
out.println("Already controlled link");
} else if (deg[admin][a] == 2 || deg[admin][b] == 2) {
out.println("Server overload");
} else if (lct[admin][a] != null && lct[admin][b] != null
&& LinkCutTree.connected(lct[admin][a], lct[admin][b])) {
out.println("Network redundancy");
} else {
out.println("Assignment done");
--deg[prevAdmin][a];
--deg[prevAdmin][b];
++deg[admin][a];
++deg[admin][b];
LinkCutTree.Node edgeNode = info.edgeNode;
LinkCutTree.cut(lct[prevAdmin][a], edgeNode);
LinkCutTree.cut(lct[prevAdmin][b], edgeNode);
if (lct[admin][a] == null) {
lct[admin][a] = new LinkCutTree.Node(0);
}
if (lct[admin][b] == null) {
lct[admin][b] = new LinkCutTree.Node(0);
}
LinkCutTree.link(lct[admin][a], edgeNode);
LinkCutTree.link(lct[admin][b], edgeNode);
info.admin = admin;
}
} else if (t == 2) {
int x = in.nextInt();
LinkCutTree.Node edgeNode = infos[Arrays.binarySearch(edges,
edge(a, b))].edgeNode;
LinkCutTree.modify(edgeNode, edgeNode, x);
} else {
int admin = in.nextInt() - 1;
if (lct[admin][a] == null || lct[admin][b] == null
|| !LinkCutTree.connected(lct[admin][a], lct[admin][b])) {
out.println("No connection");
} else {
int res = LinkCutTree.query(lct[admin][a], lct[admin][b]);
out.println(res + " security devices placed");
}
}
}
}
static long edge(int u, int v) {
return ((long) Math.min(u, v) << 32) + Math.max(u, v);
}
static class Info {
int admin;
LinkCutTree.Node edgeNode;
long edge;
public Info(int admin, LinkCutTree.Node edgeNode, long edge) {
this.admin = admin;
this.edgeNode = edgeNode;
this.edge = edge;
}
}
static class LinkCutTree {
static int queryOperation(int leftValue, int rightValue) {
return leftValue + rightValue;
}
static int getNeutralValue() {
return 0;
}
public static class Node {
int nodeValue;
int subTreeValue;
int size;
boolean revert;
Node left;
Node right;
Node parent;
Node(int value) {
nodeValue = value;
subTreeValue = value;
size = 1;
}
boolean isRoot() {
return parent == null
|| (parent.left != this && parent.right != this);
}
void push() {
if (revert) {
revert = false;
Node t = left;
left = right;
right = t;
if (left != null) {
left.revert = !left.revert;
}
if (right != null) {
right.revert = !right.revert;
}
}
}
void update() {
subTreeValue = queryOperation(
queryOperation(getSubTreeValue(left), nodeValue),
getSubTreeValue(right));
size = 1 + getSize(left) + getSize(right);
}
}
static int getSize(Node root) {
return root == null ? 0 : root.size;
}
static int getSubTreeValue(Node root) {
return root == null ? getNeutralValue() : root.subTreeValue;
}
static void connect(Node ch, Node p, Boolean isLeftChild) {
if (ch != null) {
ch.parent = p;
}
if (isLeftChild != null) {
if (isLeftChild) {
p.left = ch;
} else {
p.right = ch;
}
}
}
static void rotate(Node x) {
Node p = x.parent;
Node g = p.parent;
boolean isRootP = p.isRoot();
boolean leftChildX = (x == p.left);
connect(leftChildX ? x.right : x.left, p, leftChildX);
connect(p, x, !leftChildX);
connect(x, g, isRootP ? null : p == g.left);
p.update();
}
static void splay(Node x) {
while (!x.isRoot()) {
Node p = x.parent;
Node g = p.parent;
if (!p.isRoot()) {
g.push();
}
p.push();
x.push();
if (!p.isRoot()) {
rotate((x == p.left) == (p == g.left) ? p : x);
}
rotate(x);
}
x.push();
x.update();
}
static Node expose(Node x) {
Node last = null;
for (Node y = x; y != null; y = y.parent) {
splay(y);
y.left = last;
last = y;
}
splay(x);
return last;
}
public static void makeRoot(Node x) {
expose(x);
x.revert = !x.revert;
}
public static boolean connected(Node x, Node y) {
if (x == y) {
return true;
}
expose(x);
expose(y);
return x.parent != null;
}
public static void link(Node x, Node y) {
makeRoot(x);
x.parent = y;
}
public static void cut(Node x, Node y) {
makeRoot(x);
expose(y);
y.right.parent = null;
y.right = null;
}
public static int query(Node from, Node to) {
makeRoot(from);
expose(to);
return getSubTreeValue(to);
}
public static void modify(Node from, Node to, int delta) {
makeRoot(from);
expose(to);
to.nodeValue = delta;
}
}
}
class InputReader {
final InputStream is;
final byte[] buf = new byte[1024];
int pos;
int size;
public InputReader(InputStream is) {
this.is = is;
}
public int nextInt() {
int c = read();
while (isWhitespace(c)) {
c = read();
}
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res = res * 10 + c - '0';
c = read();
} while (!isWhitespace(c));
return res * sign;
}
int read() {
if (size == -1) {
throw new InputMismatchException();
}
if (pos >= size) {
pos = 0;
try {
size = is.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (size < = 0) {
return -1;
}
}
return buf[pos++] & 255;
}
static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}