Baltic Olympiad in Informatics: 2018 Day 2, Problem 1
Fredrik is at home, playing with a custom-built model railway which he is very proud of. The railway consists of
However, Fredrik is becoming bored with his circling train and decides to add a train switch to every segment, which he could use to cause derailing accidents and other exciting scenarios. But the switches also need electricity. And not just any kind of electricity; they specifically need alternating current.
The way you get alternating current, Fredrik figures, is by having current that goes in both directions. Each wire only gives current in one direction (either clockwise or counter-clockwise) but Fredrik is free to decide which. Thus, what he wants to do is to make a decision about the direction of the current in each wire, so that every track segment is covered by both a wire with clockwise-directed current and a wire with counter-clockwise-directed current.
Can you help Fredrik with this task?
A solution to the first sample. The curved arrows outside the railway represent the wires that provide electricity. The direction of each arrow represents Fredrik's choice of direction of the current (with the blue and red colors emphasizing the different directions). Note that all arrows could have been reversed to get the other valid solution: 11010
.
Input
The first line contains two integers
The next
Output
Output a single line with 0
or 1
. The 0
if the current in the 1
if it should be directed counter-clockwise. If there are multiple solutions you may output any of them.
If there is no valid solution, output impossible
.
Constraints
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
Group | Points | Limits | Additional Constraints |
---|---|---|---|
1 | 13 | None | |
2 | 20 | None | |
3 | 22 | None | |
4 | 19 | No wire has | |
5 | 26 | None |
Sample Input 1
10 5
1 5
6 7
5 1
7 2
2 4
Sample Output 1
00101
Sample Input 2
10 5
1 4
2 5
4 7
6 10
8 1
Sample Output 2
impossible
Sample Input 3
5 2
1 5
3 3
Sample Output 3
impossible
Sample Input 4
5 3
3 3
2 1
4 2
Sample Output 4
101
Comments