Memory limit: 256 megabytes

It is not easy to keep the children engaged in the day care. Someone's missing Mommy, someone's finger hurts, someone can't decide what they want to play next... Now Natalya Alexandrovna invented a new game. She prepared a bunch of pairs of cards with pictures. There are N desks in her classroom and Natalya Alexandrovna picks N pairs from her supplies and lays two cards on each desk. Of the two cards, one lies face up and the other face down. Even more, from each pair, exactly one card is face up. In the beginning of the game, the K (K ≤N) kids in her care on that day sit down at the desks, at most one kid at each desk. In the first minute of the game, each kid has to peek at the card laid on the desk face down and move to the desk where the same picture is face up. After that the kids continue to move according to the same rules every following minute. The best part of the game is that kids can continue playing until the parents come to collect them. And even if some kids are collected before others, the remaining ones can still carry on. There's only one problem: Natalya Alexandrovna is unable to tell the parents the location of their child at any given moment. She agrees to give you the initial positions of the kids and information about all cards (even the ones laid face down) to help her respond fast to the parents looking for their offspring.

Input

The first line of input contains the integers N and K (1 ≤K ≤N ≤10⁵). The following N lines contain two integers each: the numbers of the pictures on the cards laid face up and face down on the i-th desk (the pictures are numbered 1…N). The following K lines also contain two integers each: the number of the desk (1…N) that was the initial position of the j-th kid and the number of minutes from the start of the game to the moment when the parents come looking for the kid (1…10⁹).

Output

Output K lines, one for each kid. The j-th line must contain a single integer, the number of the desk at which the j-th kid is sitting when his/her parents arrive.

Example

Задача 8. Odd Factor (NEERC 2011 Western Subregional Contest. Problem I)

Input file: oddfactor.in

Output file: oddfactor.out

Time limit: 2 seconds

Memory limit: 64 megabytes

Odd factor of an undirected graph is a spanning subgraph (that is, a subgraph containing all vertices of the original graph) where the local degree of each vertex is odd. Given an undirected graph, either construct any of its odd factors or verify that none exists.

Input

The first line of input contains the number of vertices n (1 ≤n ≤10⁵) and the number of edges m (0 ≤m ≤10⁶) of the graph. The follwing m lines describe the edges, with each edge given on a separate line as two integers a_i and b_i (1 ≤a_i; b_i ≤n; a_i ≠ b_i), the numbers of the vertices the edge connects.

Output

If an odd factor can be constructed, the first line of output must contain the number of edges in the factor and the following lines must list the edges. If there's no odd factor, output -1 as the answer.

Examples

Задача 9. Kingdom Roadmap(NEERC 2011. Problem K)

Input file: kingdom.in

Output file: kingdom.out

Time limit: 2 seconds

Memory limit: 64 megabytes

The Kingdom consists of n cities connected by n − 1 roads in such a way that there is exactly one way to travel from one city to another. The King is a busy man and he constantly travels from city to city. Unfortunately, during one of his travels one of the roads got damaged and needed serious repairs. As a result, the King was unable to reach his destination in time.

After the incident the King decided to improve reliability of the road system. It was decided that the improved road system shall be able to withstand one damaged road, i.e. there shall always be a path from one city to another even when one road in the Kingdom is damaged. As always, the budget is limited so you need to minimize the number of new roads.

Your task is to build as few new roads as possible so that there is always a path between any two cities even if one of the roads gets unusable for any reason. There may be multiple optimal solutions. Any one can be used.

Input

The first line of the input file contains integer n — the number of cities in the kingdom (2 ≤ n ≤ 100 000). The following n − 1 lines contain two integers ui, vi each — the cities connected by i-th road

(1 ≤ ui, vi ≤ n).

Output

The first line of the output file shall contain one integer k — the number of roads to be built. The following k lines shall contain two integers ai, bi each — the cities which should be connected by i-th new road (1 ≤ ai, bi ≤ n).

Поиск по сайту: