Company Hierarchy Verification

You are given a company's organizational structure in the form of an undirected tree. The organization is intended to be a four-layer hierarchy:

• Level 0: 1 node (CEO)
• Level 1: 3 nodes
• Level 2: 9 nodes
• Level 3: 27 nodes

This means there should be exactly 40 nodes in total. The input provides the number of employees and a list of direct connections between employees. Each connection is bidirectional and can be used to traverse the tree.

Your task is to verify whether the given structure forms a valid hierarchy as specified. Output Valid if it does, and Invalid otherwise.

Note: Even though the connections are undirected, they represent a tree with the expected layered structure. The root (CEO) is assumed to be the unique node having exactly 3 adjacent nodes.

inputFormat

The first line contains two integers n and m, where n is the number of employees and m is the number of connections.

Each of the following m lines contains two integers u and v (separated by space) representing a bidirectional connection between employees u and v.

Input Format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

outputFormat

Output a single line containing either Valid or Invalid. This indicates whether the given structure forms the desired four-layer hierarchy.

## sample

40 39
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
5 14
5 15
5 16
6 17
6 18
6 19
7 20
7 21
7 22
8 23
8 24
8 25
9 26
9 27
9 28
10 29
10 30
10 31
11 32
11 33
11 34
12 35
12 36
12 37
13 38
13 39
13 40

Valid