
Peter Pan was given career guidance to help determine his future profession. As he
does not want to grow up, he ran away and sought shelter in Neverland. There are
two rivers in Neverland, flowing from west to east. On the shore of the first river,
there are
Citizens of Neverland plan to establish
A pair of cities is called connected if it is possible to reach the second city starting from the first, and vice versa. While traveling, it is allowed to use both flight routes and rivers. Peter Pan wants to determine the route directions in order to minimize the largest set of cities in which no pair of cities is connected. Help Peter Pan and determine how to direct the routes and what would the size of the mentioned set be in that case.
Input Specification
The first line contains positive integers
The
Output Specification
In the first line print the least possible size of the maximum set of cities in which no pair of cities is connected.
In the second line print a sequence of characters 0
or 1
separated by spaces which denote the directions of
the flight routes. The character 0
means that the flight takes off from the first river and lands on the
second river, and conversely for 1
. If there is more than one solution, output any.
Constraints
Subtask | Points | Constraints |
---|---|---|
No additional constraints. |
Sample Input 1
5 3
4
1 2
2 3
3 1
5 3
Sample Output 1
1
1 1 0 0
Explanation for Sample Output 1
If the flights are directed as shown in the output, it is possible to reach any city starting from any other
city. Therefore, the largest set containing no pair of connected cities is a singleton. For example, it's
possible to reach city
Sample Input 2
6 6
4
1 2
3 2
4 3
5 6
Sample Output 2
9
1 0 1 1
Sample Input 3
8 7
7
1 3
2 1
3 4
5 6
6 5
6 7
8 7
Sample Output 3
5
1 0 1 1 0 1 0
Comments