530. Recruiting
Time limit per test: 1
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Hurry! Two wellknown software companies are recruiting programmers. Initially the total number of unemployed programmers is
n. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.
Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if
a is a friend of
b then
b is a friend of
a.
All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.
As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.
Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.
Input
The first line of the input contains two integers
n and
m (3 ≤
n ≤ 10
^{5}, 2 ≤
m ≤ 2 · 10
^{5}) — the number of programmers and the number of pairs of friends among them, respectively. The programmers are numbered with integers from 1 to
n. The geniuses have numbers 1, 2 and 3. The next
m lines decribe pairs of friends. Each line contains a pair of integers
a_{i},
b_{i} (1 ≤
a_{i},
b_{i} ≤
n,
a_{i} ≠
b_{i}), where
a_{i} and
b_{i} are friends in the
ith pair. No pair occurs more than once, even in reverse order.
Output
Output the number of the company (1 or 2) which will recruit two geniuses. It is guaranteed that one company will hire two geniuses.
Example(s)
sample input

sample output

4 3
1 4
2 4
3 4

1

sample input

sample output

6 6
1 4
1 5
2 5
2 6
3 6
3 4

2

Note
In the second example, programmers form a symmetric cycle of length 6. If the first company starts with a genius (say, number 1), the second one takes the programmer number 5. Then if the first company recruits the 4th programmer, the second one recruits the 2nd genius, and now it is closer to the 3rd genius. Otherwise, if the first company starts with a usual programmer (say, number 4), the second company takes the 1st genius and afterwards also wins. The remaining cases are considered symmetrically. In all the cases the second company has a strategy of recruiting two geniuses.