Submit solution
Points:
15 (partial)
Time limit:
0.6s
Java 8
1.0s
Memory limit:
162M
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
A graph has vertices and
edges. When a vertex is deleted, all incident edges are deleted.
Given a sequence of vertices to be deleted one by one, count the number of connected components
before and after each deletion.
Constraints
All vertices are labeled from to
.
Input Specification
The first line contains two space-separated integers, and
.
Each of the next lines contains two space-separated integers,
and
,
indicating that
and
are connected with an edge.
Next, a single integer follows on its own line, indicating the number of
vertices that will be deleted.
lines follow, each indicating a vertex that is to be deleted. A vertex will be deleted at most once.
Output Specification
Output lines. On line
, output the number of connected components after the first
vertices have been deleted.
Sample Input
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
Sample Output
1
1
1
2
3
3
Comments
what are the restrictions on k? EDIT: nevermind obviously k <= m