A newly planned city has
The city planners want to find the busiest intersections. An intersection is called a hub if the number of roads meeting at it (its degree) is at least
Your task is to count how many intersections are hubs.
This is your first step into graphs: you only need to build the structure and count connections at each node — no traversal required yet.
The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the number of intersections, the number of roads, and the hub threshold.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning there is a two-way road between intersections KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Print a single integer — the number of hubs.
Input
6 5 3
1 2
1 3
1 4
2 3
5 61Intersection KaTeX can only parse string typed expression has degree KaTeX can only parse string typed expression (roads to KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, KaTeX can only parse string typed expression). Every other intersection has degree less than KaTeX can only parse string typed expression. So there is exactly one hub.
Example 2:
Input
4 0 04There are no roads, so every intersection has degree KaTeX can only parse string typed expression. Since KaTeX can only parse string typed expression, all KaTeX can only parse string typed expression intersections qualify as hubs.
Example 3:
Input
5 4 4
1 2
1 3
1 4
1 51Intersection KaTeX can only parse string typed expression is connected to all four others, giving it degree KaTeX can only parse string typed expression. The others have degree KaTeX can only parse string typed expression. Only intersection KaTeX can only parse string typed expression is a hub.