交通问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一个这样的城市:它的公路都是东西走向或南北走向的,公路的编号都是从1开始的连续自然数。而每一个公路相交处都有一个交通岗,并配有红绿灯。这个城市里边的人在任何时候都非常遵守交通规则,只有在绿灯的时候,才通过交通岗(包括转弯),绝对不会闯红灯。而且他们只会在交通岗改变他们的行车方向。城市里的每条公路的两端都与别的城市相连。
2010年的一天,恐怖分子突然控制了这个城市,破坏了这个城市的交通系统,使得每个交通岗的灯都变成了绿灯。但是如果一旦有车通过了这个交通岗,这个岗则马上变成了红灯,别的车辆无法再从这个交通岗通过。也就是,每个岗只允许一个车次通过。
这一天恰好在城市中有n辆车,你的任务就是分析这些车辆能不能逃离到别的城市。

Input

输入数据有多组组成。每一组的第1行由3个整数组成:n,m,k,分别表示这个城市水平、竖直公路的条数,以及在城市里的车的数量。
接下来的k行,表示每个汽车的坐标(x,y),既x行y列有个小车。每个小车开始都在一个交通岗停靠,一旦开出这个交通岗,这个交通岗的交通灯也变成红色。
当n,m,k分别为0,0,0时,结束输入。这组不用输出。

Output

输出的每组数据输出两行,第1行为“Scenario Ⅰ”,其中Ⅰ表示组数。
如果这些车辆都可以逃离,则在第2行输出“Solution exists”;否则输出“No solution available”。

Sample Input

5 5 12
1 2
1 3
2 1
2 4
3 1
3 2
3 5
4 1
4 2
5 2
5 3
5 4
4 3 6
1 3
1 2
2 1
2 2
3 1
4 2
3 3 9
1 1
1 2
1 3
2 1
2 2 
2 3
3 1
3 2
3 3
0 0 0

Sample Output

Scenario 1
No solution available
Scenario 2
Solution exists
Scenario 3
No solution available

Hint

 

Source