Today is April 1st, 2100. Now Guangzhou is a very very big city. Since the number of traffic accidents increased last month, the mayor asked Mr. Chopsticks to investigate the traffic condition of the city.
After studying the map of Guangzhou for a while, Mr. Chopsticks has some ideas. Guangzhou can be considered as a rectangular grid with 50000 horizontal streets running west-east (labeled with y-coordinates from 1 to 50000) and 50000 vertical streets running north-south (labeled with x-coordinates from 1 to 50000). All streets are two-way streets. A crossroad is an intersection of a horizontal street and a vertical street, so a crossroad can be represented by (x, y), where x and y are coordinates of the horizontal street and vertical street respectively. Since there are too many streets, traffic lights are not placed at all crossroads. Given two crossroads (x1, y1) and (x2, y2), a path between these two crossroads is said to be good if the length of the path is |x1 – x2| + |y1 – y2| and there exist a traffic light at each turn of this path. Of course, a path must be along the streets, and a turn can only be at a crossroad.
Now given locations of all traffic lights in Guangzhou, Mr. Chopsticks wants to check whether there exists at least one good path between every pair of traffic lights. As Mr. Chopsticks is busy in preparing ACMICPC 2100, he asks you for help.