One of Burak's friends, Berfinnur, is new in the programming and gaming industry. She is building a simple puzzle game. In the game, the player is moving on the roads that connect floating islands. When the player passes a road, the road is destroyed. Player's objective is to destroy all the roads and arrive at any of the floating islands so that player can pass the next level. Since the road will be destroyed when the player passes, the player cannot use the same road to travel back. Berfinnur is good at the coding part however she is having a hard time while designing levels.

Luckily, Burak is a level designer and works for a game company. Berfinnur asks him for help with her indie game. Now Burak needs to design levels for the game. He wants to help his friend and design several levels. However, since Burak is too busy, he is not able to test whether the designed levels are valid and playable or not. This time Burak asks to help from you.

Can you help Burak to determine all levels are designed well and valid?

To validate a level, you need to determine that a player is able to arrive any floating island by starting from any floating island.

Input

In the first line, two integer will be given: The number of the floating islands, \(\mathbf{I}\), and the number of the roads, \(\mathbf{R}\).

Next \(\mathbf{R}\) lines include the road information. There are two integers each line that consists of the islands connected by \(i^{th}\) road.

• 2 \(\leq\) \(\mathbf{I}\) \(\leq\) 250
• 1 \(\leq\) \(\mathbf{R}\) \(\leq\) 31125

The followings are guaranteed:

• Island names are integers between 0 (included) and 250 (not included)
• There is not a road that connects the same island (loop road).
• There is not multiple roads connection between same islands; in other words, there is maximum one connection between two islands.
• Each island is connected to at least one another island.

Output

Print VALID if the level is appropriate; otherwise, print INVALID.

Examples

Input 1:

3 2
0 1
0 2

Output 1:

VALID

Input 2:

4 3
0 1
0 2
0 3

Output 2:

INVALID

Explanation

Input 1:

One way is the following:

• Start from island 2.
• From island 2, go to island 0.
• From island 0, go to island 1

Input 2:

There is no way to destroy all roads.