Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

I Hate Long Description

By sarwarIT · Limits 1s, 512 MB

There are N cities in the country AjobDesh and M one way roads connecting the cities.

There lives exactly one AjobPrani in each of the N cities. Every AjobPrani must visit at least one other AjobPrani if there is a path to visit. If possible then he should also return to his home town.

Find how many AjobPrani are unable to return to his home town.

Input

First line contains the number of test cases T(1≤ T ≤10).

For each test case:

First line consists of two integers denoting N(1≤ N ≤100000) and M(0≤ M ≤200000).

Next M lines consist of two integers A and B denoting there is a directed road from A to B (1≤ A,B ≤N).The graph can contain self loops.

Output

For every test case, you need to print “Case T: ” (where T is the test case number) followed by the number of AjobPrani who can’t return.

Sample

InputOutput
1
5 6
1 2
2 3
2 5
5 3
5 1
4 5

Case 1: 1


Route for each AjobPrani:
AjobPrani 1: 1->2->5->1
AjobPrani 2: 2->5->1->2
AjobPrani 3: no way to visit any other AjobPrani
AjobPrani 4: 4->5 [can not return to 4]
AjobPrani 5: 5->1->2->5
So, only AjobPrani 4 can not return to his home town.

    Discussion

    Statistics


    52% Solution Ratio

    NirjhorEarliest, 3M ago

    EdgedancerFastest, 0.1s

    EdgedancerLightest, 8.7 MB

    NirjhorShortest, 1115B

    Submit

    Login to submit

    Editorial

    For any node in an SCC consisting of 2 or more node we can visit any other city and come back to tha...

    Related Contests

    SELISE Coding Challenge 2020 Ended 3M ago