No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

There is a new game "thimbles" in the Berland's casino. The rules of the game are pretty simple. Croupier places N thimbles on the table and puts a ball under the first of them. Afterwards he shuffles the thimbles and asks a player "Where is the ball?". If the player guesses right, he wins, otherwise he loses. Artful professor Zhuglov noticed, that during the whole day the croupier shuffles thimbles with exactly M swap operations. The set of operations remains invariable, but their order may vary. Swap operation, term introduced by professor Zhuglov, is defined as interchange of two thimbles in positions Ai and Bi. Professor Zhuglov is your scientific advisor, and you are to write a program for him that will determine all possible thimbles that can have the ball inside after the shuffling.

The first line of the input file contains integer numbers N and M (2 <= N <= 100, 1 <= M <= 1000). Each of the following M lines contains two integer numbers Ai and Bi -- swap operation description (1 <= Ai < Bi <= N).

Output the answer for the problem. Numbers can be printed in any order. Adjacent numbers should be delimited by a space.

Input

4 3

1 2

1 2

2 3

1 2

1 2

2 3

Output

1 3

There are 3 ways of applying the operations. They are (1,2)-(1,2)-(2,3), (1,2)-(2,3)-(1,2) and (2,3)-(1,2)-(1,2). In the first case a ball will be moved form 1 to 2, and with the 2-nd operation will be returned to 1. In the second case a ball will be moved from 1 to 2 then from 2 to 3. In the third case a ball will be moved by the second operation from 1 to 2 and will be returned to 1 by the third operation.

Author: | Andrew V. Lazarev |

Resource: | ACM ICPC 2004-2005, NEERC, Southern Subregional Contest |

Date: | Saratov, October 7, 2004 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/06/2021 20:30:11 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|