added working NWERC11C
[the-user-spoj:the-user-spoj.git] / MMCUT.cpp
1 #include <cstdio>
2 #include <cstdlib>
3 #include <stdint.h>
4 #include <string>
5 #include <iostream>
6 #include <unistd.h>
7 #include <sys/time.h>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <cmath>
12 #include <algorithm>
13 using namespace std;
14
15 typedef unsigned long long ull;
16
17 inline FILE& operator>>(FILE& f, char*& d)
18 {
19     int s = 20;
20     d = (char*)malloc(s);
21     int chr;
22     int i = 0;
23     do
24     {
25         chr = fgetc(&f);
26         if(chr == EOF)
27             goto OPERATOR_RSHIFT_FILE_CHAR_PTR_end;
28     }
29     while(chr == '\n' || chr == '\r' || chr == '\t' || chr == ' ');
30     do
31     {
32         if(i == s)
33         {
34             s *= 2;
35             d = (char*)realloc(d, s);
36         }
37         d[i] = chr;
38         chr = fgetc(&f);
39         ++i;
40     }
41     while(chr != EOF && chr != '\n' && chr != '\r' && chr != '\t' && chr != ' ');
42     OPERATOR_RSHIFT_FILE_CHAR_PTR_end:;
43     d = (char*)realloc(d, i+1);
44     d[i] = '\0';
45     return f;
46 }
47 inline FILE& operator>>(FILE& f, char& chr)
48 {
49     int x;
50     do
51     {
52         x = fgetc(&f);
53         if(x == EOF)
54         {
55             chr = '\0';
56             return f;
57         }
58     }
59     while(x == '\n' || x == '\r' || x == '\t' || x == ' ');
60     chr = x;
61     return f;
62 }
63 inline FILE& operator>>(FILE& f, int& x)
64 {
65     char *d;
66     f >> d;
67     x = atoi(d);
68     free(d);
69     return f;
70 }
71 inline FILE& operator>>(FILE& f, ull& x)
72 {
73     fscanf(&f, "%llu", &x);
74     return f;
75 }
76 inline FILE& operator>>(FILE& f, float& x)
77 {
78     char *d;
79     f >> d;
80     x = atof(d);
81     free(d);
82     return f;
83 }
84 inline FILE& operator>>(FILE& f, double& x)
85 {
86     char *d;
87     f >> d;
88     x = atof(d);
89     free(d);
90     return f;
91 }
92 inline FILE& operator>>(FILE& f, long double& x)
93 {
94     fscanf(&f, "%LE", &x);
95     return f;
96 }
97 inline FILE& operator>>(FILE& f, string& str)
98 {
99     char *d;
100     f >> d;
101     str.~string();
102     new (&str) string(d);
103     free(d);
104     return f;
105 }
106 inline FILE& operator<<(FILE& f, const char *str)
107 {
108     fputs(str, &f);
109     return f;
110 }
111 inline FILE& operator<<(FILE& f, int x)
112 {
113     fprintf(&f, "%d", x);
114     return f;
115 }
116 inline FILE& operator<<(FILE& f, size_t x)
117 {
118     fprintf(&f, "%u", x);
119     return f;
120 }
121 inline FILE& operator<<(FILE& f, ull x)
122 {
123     fprintf(&f, "%llu", x);
124     return f;
125 }
126 inline FILE& operator<<(FILE& f, double x)
127 {
128     fprintf(&f, "%.12f", x);
129     return f;
130 }
131 inline FILE& operator<<(FILE& f, long double x)
132 {
133     fprintf(&f, "%.12Lf", x);
134     return f;
135 }
136 inline FILE& operator<<(FILE& f, const string& str)
137 {
138     f << str.c_str();
139     return f;
140 }
141 inline FILE& operator<<(FILE& f, char c)
142 {
143     fputc(c, &f);
144     return f;
145 }
146 struct _endofline
147 {
148 } eol;
149 struct _flush
150 {
151 } clearbuff;
152 inline FILE& operator<<(FILE& f, const __typeof__(eol)&)
153 {
154     fputc('\n', &f);
155 //     fflush(&f);
156     return f;
157 }
158 inline FILE& operator<<(FILE& f, const __typeof__(clearbuff)&)
159 {
160     fflush(&f);
161     return f;
162 }
163
164 FILE& lin(*stdin);  // low-level-in
165 FILE& lout(*stdout);    // low-level-out
166 FILE& lerr(*stderr);
167
168 typedef pair<int,int> PII;
169
170 int main()
171 {
172     int n, m;
173     lin >> n >> m;
174     --n; // Ignore root
175     vector<vector<int> > adj(n);
176     vector<int> visited(n);
177     vector<bool> fauleArme(n);
178     for(int i = 0; i != m; ++i)
179     {
180         int x, y;
181         lin >> x >> y;
182         if(x != n && y != n)
183         {
184             adj[x].push_back(y);
185             adj[y].push_back(x);
186         }
187         else if(x == n)
188             fauleArme[(y)] = true;
189         else if(y == n)
190             fauleArme[(x)] = true;
191     }
192     if(!m)
193     {
194         lout << "0\n";
195         return 0;
196     }
197     for(int i = 0; i != n; ++i)
198     {
199         if(!visited[i])
200         {
201             stack<pair<int, bool> > tv;
202             tv.push(make_pair(i, false));
203             vector<int> currFauleArme;
204             while(!tv.empty())
205             {
206                 pair<int, bool> c = tv.top();
207                 tv.pop();
208                 if(!visited[c.first])
209                 {
210                     if(fauleArme[(c.first)])
211                         currFauleArme.push_back(c.first);
212                     visited[c.first] = (c.second ? 2 : 1);
213                     for(int i = 0; i != adj[c.first].size(); ++i)
214                     {
215                         if(visited[adj[c.first][i]] == 0)
216                             tv.push(make_pair(adj[c.first][i], !c.second));
217                         else if(visited[adj[c.first][i]] == (c.second ? 2 : 1))
218                             goto fail;
219                     }
220                 }
221             }
222             if(currFauleArme.size() > 0)
223             {
224                 int s = visited[currFauleArme[0]];
225                 for(int i = 1; i != currFauleArme.size(); ++i)
226                     if(visited[currFauleArme[i]] != s)
227                         goto fail;
228             }
229         }
230     }
231     lout << "1\n";
232     if(false)
233     {
234         fail:
235         lout << "2\n";
236     }
237 }
238