Submission #17,214

2025-06-03 16:14:04

pypy3

Accepted 100/100

935ms

106828 KiB

from sys import stdin
input=stdin.readline

def solv():
 n,m,q=map(int,input().split())
 G=[[] for i in range(n+m)]
 for i in range(q):
  u,v=map(int,input().split())
  G[u-1].append(v-1+n)
  G[v-1+n].append(u-1)
 seen=set()
 comp=0
 for i in range(n+m):
  if i not in seen:
   comp+=1
   cur=[i]
   seen.add(i)
   while cur:
    tmp=set()
    for v in cur:
     for w in G[v]:
      if w not in seen:
       tmp.add(w)
       seen.add(w)
    cur=tmp
 return comp

print(solv()-1)

	Sum	Test	Verdict	Time	Memory
0	0/0
		1	Accepted	43ms	19444 KiB
		2	Accepted	39ms	19584 KiB
		3	Accepted	45ms	19540 KiB
1	10/10
		4	Accepted	39ms	19764 KiB
		5	Accepted	45ms	19520 KiB
		6	Accepted	46ms	19356 KiB
		7	Accepted	41ms	19408 KiB
		8	Accepted	45ms	19424 KiB
		9	Accepted	39ms	19560 KiB
		10	Accepted	43ms	19388 KiB
		11	Accepted	39ms	19532 KiB
		12	Accepted	39ms	19436 KiB
		13	Accepted	45ms	19436 KiB
		14	Accepted	45ms	19576 KiB
		15	Accepted	39ms	19436 KiB
		16	Accepted	45ms	19428 KiB
		17	Accepted	39ms	19412 KiB
		18	Accepted	39ms	19600 KiB
		19	Accepted	45ms	19380 KiB
2	8/8
		20	Accepted	41ms	19444 KiB
		21	Accepted	45ms	19600 KiB
		22	Accepted	46ms	19500 KiB
		23	Accepted	41ms	19424 KiB
		24	Accepted	45ms	19476 KiB
		25	Accepted	39ms	19436 KiB
		26	Accepted	46ms	19444 KiB
3	9/9
		27	Accepted	43ms	19360 KiB
		28	Accepted	39ms	19384 KiB
		29	Accepted	43ms	19592 KiB
		30	Accepted	39ms	19392 KiB
		31	Accepted	39ms	19432 KiB
4	8/8
		32	Accepted	41ms	19564 KiB
		33	Accepted	43ms	19588 KiB
		34	Accepted	45ms	19544 KiB
		35	Accepted	41ms	19624 KiB
		36	Accepted	46ms	19428 KiB
		37	Accepted	39ms	19436 KiB
		38	Accepted	45ms	19436 KiB
5	20/20
		39	Accepted	41ms	19788 KiB
		40	Accepted	43ms	19760 KiB
		41	Accepted	45ms	19560 KiB
		42	Accepted	41ms	19652 KiB
		43	Accepted	45ms	19616 KiB
		44	Accepted	46ms	19704 KiB
		45	Accepted	41ms	19516 KiB
		46	Accepted	39ms	19448 KiB
		47	Accepted	45ms	19480 KiB
		48	Accepted	50ms	21192 KiB
		49	Accepted	41ms	19528 KiB
		50	Accepted	39ms	19636 KiB
		51	Accepted	45ms	19584 KiB
		52	Accepted	41ms	19608 KiB
		53	Accepted	45ms	19480 KiB
		54	Accepted	41ms	19432 KiB
		55	Accepted	46ms	19536 KiB
		56	Accepted	43ms	19432 KiB
		57	Accepted	39ms	19428 KiB
		58	Accepted	39ms	19540 KiB
		59	Accepted	39ms	19404 KiB
		60	Accepted	45ms	19616 KiB
		61	Accepted	46ms	19604 KiB
		62	Accepted	39ms	19576 KiB
		63	Accepted	45ms	19428 KiB
		64	Accepted	41ms	19708 KiB
		65	Accepted	39ms	19688 KiB
		66	Accepted	46ms	19432 KiB
		67	Accepted	39ms	19460 KiB
6	10/10
		68	Accepted	45ms	19672 KiB
		69	Accepted	41ms	19856 KiB
		70	Accepted	45ms	19840 KiB
		71	Accepted	46ms	19780 KiB
		72	Accepted	46ms	19436 KiB
		73	Accepted	46ms	19488 KiB
		74	Accepted	41ms	19620 KiB
		75	Accepted	61ms	21676 KiB
		76	Accepted	48ms	19788 KiB
		77	Accepted	41ms	19784 KiB
		78	Accepted	41ms	19856 KiB
		79	Accepted	46ms	19696 KiB
		80	Accepted	46ms	19684 KiB
		81	Accepted	41ms	19680 KiB
		82	Accepted	39ms	19688 KiB
		83	Accepted	46ms	19692 KiB
		84	Accepted	50ms	21132 KiB
		85	Accepted	41ms	19792 KiB
		86	Accepted	48ms	19824 KiB
		87	Accepted	41ms	19684 KiB
		88	Accepted	52ms	21136 KiB
		89	Accepted	39ms	19748 KiB
7	10/10
		90	Accepted	54ms	21412 KiB
		91	Accepted	71ms	22592 KiB
		92	Accepted	50ms	21252 KiB
		93	Accepted	50ms	21340 KiB
		94	Accepted	52ms	21228 KiB
		95	Accepted	46ms	21228 KiB
		96	Accepted	45ms	21236 KiB
		97	Accepted	50ms	21056 KiB
		98	Accepted	52ms	21224 KiB
		99	Accepted	45ms	21092 KiB
		100	Accepted	43ms	21120 KiB
		101	Accepted	50ms	21228 KiB
		102	Accepted	45ms	21208 KiB
		103	Accepted	46ms	19776 KiB
		104	Accepted	39ms	19544 KiB
		105	Accepted	46ms	19692 KiB
		106	Accepted	41ms	19960 KiB
		107	Accepted	41ms	19928 KiB
		108	Accepted	52ms	21276 KiB
		109	Accepted	50ms	21232 KiB
		110	Accepted	50ms	21228 KiB
		111	Accepted	45ms	21276 KiB
		112	Accepted	45ms	21216 KiB
		113	Accepted	46ms	19840 KiB
8	10/10
		114	Accepted	165ms	30508 KiB
		115	Accepted	108ms	26096 KiB
		116	Accepted	94ms	26284 KiB
		117	Accepted	108ms	26296 KiB
		118	Accepted	100ms	26424 KiB
		119	Accepted	122ms	26436 KiB
		120	Accepted	71ms	25228 KiB
		121	Accepted	87ms	25288 KiB
		122	Accepted	85ms	25576 KiB
		123	Accepted	72ms	25576 KiB
		124	Accepted	108ms	30944 KiB
		125	Accepted	126ms	31464 KiB
		126	Accepted	116ms	29928 KiB
		127	Accepted	107ms	30336 KiB
		128	Accepted	96ms	26544 KiB
		129	Accepted	67ms	24124 KiB
		130	Accepted	79ms	23932 KiB
		131	Accepted	57ms	22092 KiB
		132	Accepted	50ms	22036 KiB
		133	Accepted	59ms	23748 KiB
		134	Accepted	52ms	23800 KiB
		135	Accepted	122ms	26072 KiB
		136	Accepted	75ms	26232 KiB
		137	Accepted	79ms	26480 KiB
		138	Accepted	92ms	26564 KiB
		139	Accepted	76ms	26088 KiB
9	15/15
		140	Accepted	935ms	94876 KiB
		141	Accepted	638ms	92384 KiB
		142	Accepted	158ms	68008 KiB
		143	Accepted	141ms	65028 KiB
		144	Accepted	140ms	65016 KiB
		145	Accepted	423ms	66580 KiB
		146	Accepted	223ms	41916 KiB
		147	Accepted	92ms	60648 KiB
		148	Accepted	92ms	60648 KiB
		149	Accepted	142ms	50020 KiB
		150	Accepted	125ms	49876 KiB
		151	Accepted	293ms	51432 KiB
		152	Accepted	361ms	95536 KiB
		153	Accepted	592ms	105316 KiB
		154	Accepted	546ms	106828 KiB
		155	Accepted	246ms	71624 KiB
		156	Accepted	340ms	76336 KiB
		157	Accepted	284ms	75964 KiB
		158	Accepted	391ms	80200 KiB
		159	Accepted	261ms	77508 KiB
		160	Accepted	351ms	66936 KiB
		161	Accepted	412ms	64920 KiB
		162	Accepted	226ms	43828 KiB
		163	Accepted	358ms	66676 KiB
		164	Accepted	667ms	74396 KiB
		165	Accepted	479ms	72952 KiB
		166	Accepted	294ms	89952 KiB
		167	Accepted	317ms	82884 KiB