Supply Distribution Network Validation

You are given a network with n shelters and m bidirectional roads connecting them. Your task is to determine whether this supply distribution network is effectively designed. A properly designed network must be a tree. In other words, the network must be connected and must not contain any cycles, which mathematically means that it should have exactly \(n-1\) edges.

The input consists of two integers n and m, followed by m pairs of integers, each representing a road connecting two shelters. Your program should output valid if the network satisfies the conditions for a tree; otherwise, it should output invalid.

inputFormat

The first line contains two integers n and m separated by a space.

The following m lines each contain two integers u and v indicating there is a road between shelter u and shelter v.

outputFormat

Output a single line containing either valid if the network is a tree, or invalid if it is not.

## sample

4 3
1 2
2 3
3 4

valid

</p>