Mystery Maze Exploration

Deep in the Taklamakan Desert, a recent archaeological discovery has revealed a mysterious underground labyrinth beneath a sand dune. Led by the famous explorer Ah Qiang, an expedition team has found the entrance to this maze. However, after entering, the team finds that the entrance has merged with the stone walls and vanished. Trapped inside a seemingly endless network of identical caves, they come across a cryptic inscription on every cave wall:

Stranger, tell me the total number of caves and roads in this maze, and I shall guide you out.

Armed with only a single movable marker (referred to as the "sign") which may be carried or temporarily left in a cave, your task as Ah Qiang is to determine the structure of the maze using as few steps as possible. Here, a "step" is defined as moving from one cave to an adjacent connected cave.

The maze is composed of a number of caves, with roads connecting some pairs of caves. In each cave, you can count how many roads (paths) lead out by the dim light. The configuration of every cave and road is identical and no permanent markings can be made; the only tool available is the single sign that you can use to mark a cave temporarily.

You have access to the following interaction library functions in your program (note: in this problem's simulated version, the maze structure will be provided via standard input):

• init: Must be called once to initialize the library.
• look(d, sign): In the current cave, this function returns in d the number of roads connected to the cave, and in sign a boolean indicating whether the sign is present (true) or absent (false).
• put_sign: Place the sign in the current cave (only allowed if you are currently carrying it).
• take_sign: Pick up the sign from the current cave (only allowed if the sign is present).
• walk(i): Move along the road numbered i to the adjacent cave. In each cave, roads are temporarily numbered in counterclockwise order starting from 0. When you first take a step, the road you take is designated as road 0 in the new cave.
• report(n, m): Report the discovered maze structure where n is the number of caves and m is the number of roads. Once this is called, your program ends.

Note: Although this is an interactive problem, in this simulated version you will receive the maze data via standard input. The first line of input provides two integers n and m representing the total number of caves and roads, respectively. The following m lines each provide two integers u and v indicating a bidirectional road between cave u and cave v (caves are numbered from 1 to n).

Your task is to simply output the two numbers, separated by a space. Use minimal steps and simulate the exploration if needed.

inputFormat

The input is provided via standard input. The first line contains two integers n and m, where n is the number of caves and m is the number of roads in the maze. This is followed by m lines, each containing two integers u and v indicating a bidirectional road between caves u and v.

outputFormat

Output two integers separated by a space: the total number of caves (n) and the total number of roads (m).

sample

5 4
1 2
2 3
3 4
4 5

5 4