Submit solution

Points:
5

Time limit:
2.0s

Memory limit:
64M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

##### DWITE Online Computer Programming Contest, November 2009, Problem 4

In a graph, each node has a *"level"* – a distance to the root (start) node. One of the special properties that could be extracted, is that if there is a connection between two nodes of the same level, then there is also a cycle of odd length in the graph, which in turn gives us more properties about the structure.

The input will contain 5 testcases: A single positive integer , followed by lines describing the graph. Each line is two integers, IDs of nodes, separated by a space. Node IDs are positive integers less than . The root (start) node has ID 1.

The output will contain 5 lines, integer count of how many pairs of nodes have a connection, such that the shortest path from 1 to each node is equal.

#### Sample Input

```
3
1 2
3 2
1 3
10
1 2
1 3
2 3
2 4
3 5
3 6
4 5
5 6
4 7
5 7
```

#### Sample Output

```
1
3
```

## Comments

Question: For the sample input, should not 4 and 6 also be a pair(2 edges from the root)?

Does anyone know?

They have to be directly connected (share an edge between them) as well as being on the same level.

It should be clarified that in the sample input and output only 2 sets of the 5 are shown

Got it