Network Game
Time limit1sMemory limit1024 MB
Given up to 50 unit segments forming a net piece, players alternately cut a segment that borders a complete unit square; decide if the first player wins and output a winning first move.
- Level
Medium7 of 10
- Topics
- Game theory, Graph, Brute force, Implementation
- Solved
- No attempts yet
Problem
Petya and Vasya found the remains of their grandfather's fishing net in the attic. Some of the ropes had rotted long ago, and the net had fallen apart into many pieces, each consisting of at most 50 ropes of unit length.
Since the remains of the net could no longer be used for their intended purpose, the brothers laid one of the found pieces on a rectangular table so that the ropes were parallel to the sides of the table, and began to play the following game.
The brothers take turns, and Petya moves first. On his turn, a player finds a rope that is a side of some complete unit square cell of the net (all four ropes forming it are intact) and cuts the chosen rope. The brother who cannot make a move loses.
You must write a program that, given a description of a piece of the net on the table, determines whether Petya can win no matter how Vasya plays, and if so, which first move he must make to do so.
Input
The first line of the input file contains the number N (1 ≤ N ≤ 50), the number of unit-length ropes that make up the piece of the net. The next N lines of the input file contain two pairs of integers each: the coordinates of the endpoints of the ropes. Each quadruple of numbers describes a unit-length segment parallel to one of the coordinate axes.
The coordinates of all points are non-negative and do not exceed 50.
Output
The first line of the output file must contain the number 1 if Petya can win no matter how Vasya plays, and the number 2 if he cannot. If Petya wins, the second line must contain the number of the rope he must cut on his first move. If there are several possible winning moves, output any of them. The ropes are numbered starting from 1 in the order in which they are given in the input file.