## Problem SOLUTION CODECHEF

You are given a *directed* tree with $N$ vertices. The edges are directed away from the root.

For each $i=1,2,3,…,N$, count the number of vertices that can possibly appear at the $i$-th position of a topological order of this tree.

That is, for each $i$, find the number of vertices $u$ such that there exists a topological order $T$ of the graph satisfying $T_{i}=u$.

### Input Format

- The first line of input will contain a single integer $T$, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains one integer $N$.
- The next $N−1$ lines describe the edges. The $i_{th}$ of these $n−1$ lines contains two space-separated integers $u_{i}$ and $v_{i}$, denoting a directed edge from $u_{i}$ to $v_{i}$.

### Output Format

For each test case, output $N$ space-separated integers on a single line.

The $i$-th of them should be the answer for the $i$-th position.

### Constraints

- $1≤T≤3000$
- $1≤N≤1_{5}$
- $1≤u_{i},v_{i}≤N$
- The input graph is a directed tree on $N$ vertices.
- The sum of $N$ across all tests does not exceed $1_{5}$.

### Sample 1:

2 4 1 2 2 3 1 4 5 3 1 3 2 1 5 1 4

1 2 3 2 1 2 4 3 3

### Explanation:

**Test case $1$:** The tree is:

It has three possible topological orders:

$[1,2,3,4]$

$[1,2,4,3]$

$[1,4,2,3]$

The counts of distinct vertices appearing at the four positions are hence $[1,2,3,2]$.

**Test case $2$:** The given tree is:

Note that as a directed tree, it’s rooted at $3$ and not $1$.

SOLUTION

from collections import defaultdict

# Function to count vertices for each position in a topological order

def count_vertices(T, edges):

# Initialize data structures to store the in-degrees, out-degrees, and counts

in_degree = defaultdict(int)

out_degree = defaultdict(int)

count = defaultdict(int)

# Populate the in-degrees and out-degrees

for u, v in edges:

out_degree[u] += 1

in_degree[v] += 1

# Initialize the queue with leaf nodes

queue = []

for u in out_degree.keys():

if out_degree[u] == 0:

queue.append(u)

count[u] = 1

# Perform a breadth-first traversal

while queue:

u = queue.pop(0)

for v in edges:

if v[0] == u:

count[v[1]] += count[u]

in_degree[v[1]] -= 1

if in_degree[v[1]] == 0:

queue.append(v[1])

return count

# Number of test cases

T = int(input())

# Iterate through each test case

for _ in range(T):

N = int(input())

edges = []

for _ in range(N – 1):

u, v = map(int, input().split())

edges.append((u, v))

# Call the function to count vertices for each position in a topological order

result = count_vertices(N, edges)

# Output the counts for each position

for i in range(1, N + 1):

print(result[i], end=” “)

print()