Submission #17,213

2025-06-03 16:06:54

python3

Accepted 100/100

847ms

87540 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	16ms	3124 KiB
		2	Accepted	16ms	3120 KiB
		3	Accepted	16ms	3124 KiB
1	10/10
		4	Accepted	16ms	3124 KiB
		5	Accepted	17ms	3152 KiB
		6	Accepted	16ms	3148 KiB
		7	Accepted	17ms	3368 KiB
		8	Accepted	16ms	2992 KiB
		9	Accepted	17ms	3080 KiB
		10	Accepted	16ms	3152 KiB
		11	Accepted	16ms	3140 KiB
		12	Accepted	17ms	3128 KiB
		13	Accepted	16ms	3128 KiB
		14	Accepted	14ms	3124 KiB
		15	Accepted	16ms	3152 KiB
		16	Accepted	16ms	3124 KiB
		17	Accepted	16ms	3136 KiB
		18	Accepted	17ms	3076 KiB
		19	Accepted	16ms	3076 KiB
2	8/8
		20	Accepted	16ms	3324 KiB
		21	Accepted	16ms	3120 KiB
		22	Accepted	16ms	3128 KiB
		23	Accepted	16ms	3124 KiB
		24	Accepted	16ms	3320 KiB
		25	Accepted	16ms	3316 KiB
		26	Accepted	16ms	3124 KiB
3	9/9
		27	Accepted	16ms	3016 KiB
		28	Accepted	14ms	2956 KiB
		29	Accepted	16ms	3140 KiB
		30	Accepted	16ms	3124 KiB
		31	Accepted	16ms	3124 KiB
4	8/8
		32	Accepted	16ms	3312 KiB
		33	Accepted	16ms	3124 KiB
		34	Accepted	16ms	3124 KiB
		35	Accepted	16ms	3124 KiB
		36	Accepted	16ms	2992 KiB
		37	Accepted	16ms	3104 KiB
		38	Accepted	16ms	2936 KiB
5	20/20
		39	Accepted	16ms	3124 KiB
		40	Accepted	16ms	3312 KiB
		41	Accepted	16ms	3136 KiB
		42	Accepted	16ms	3124 KiB
		43	Accepted	14ms	3096 KiB
		44	Accepted	16ms	2940 KiB
		45	Accepted	16ms	2952 KiB
		46	Accepted	16ms	3156 KiB
		47	Accepted	16ms	3144 KiB
		48	Accepted	17ms	3312 KiB
		49	Accepted	16ms	3124 KiB
		50	Accepted	17ms	3124 KiB
		51	Accepted	16ms	3120 KiB
		52	Accepted	16ms	3160 KiB
		53	Accepted	17ms	3120 KiB
		54	Accepted	16ms	3120 KiB
		55	Accepted	17ms	3056 KiB
		56	Accepted	17ms	3116 KiB
		57	Accepted	17ms	3316 KiB
		58	Accepted	16ms	3116 KiB
		59	Accepted	16ms	3096 KiB
		60	Accepted	16ms	3124 KiB
		61	Accepted	16ms	3128 KiB
		62	Accepted	14ms	3172 KiB
		63	Accepted	17ms	3124 KiB
		64	Accepted	16ms	3320 KiB
		65	Accepted	16ms	3032 KiB
		66	Accepted	16ms	3120 KiB
		67	Accepted	16ms	3320 KiB
6	10/10
		68	Accepted	16ms	3124 KiB
		69	Accepted	17ms	3124 KiB
		70	Accepted	16ms	3124 KiB
		71	Accepted	17ms	3132 KiB
		72	Accepted	16ms	3160 KiB
		73	Accepted	16ms	2996 KiB
		74	Accepted	16ms	3124 KiB
		75	Accepted	26ms	3464 KiB
		76	Accepted	17ms	3124 KiB
		77	Accepted	17ms	2996 KiB
		78	Accepted	16ms	3172 KiB
		79	Accepted	17ms	3024 KiB
		80	Accepted	16ms	3128 KiB
		81	Accepted	17ms	3120 KiB
		82	Accepted	17ms	3132 KiB
		83	Accepted	16ms	3124 KiB
		84	Accepted	17ms	3016 KiB
		85	Accepted	16ms	2984 KiB
		86	Accepted	16ms	2980 KiB
		87	Accepted	16ms	3184 KiB
		88	Accepted	16ms	3148 KiB
		89	Accepted	17ms	3116 KiB
7	10/10
		90	Accepted	17ms	3124 KiB
		91	Accepted	48ms	4916 KiB
		92	Accepted	17ms	3320 KiB
		93	Accepted	17ms	3124 KiB
		94	Accepted	17ms	3212 KiB
		95	Accepted	17ms	3124 KiB
		96	Accepted	17ms	3180 KiB
		97	Accepted	16ms	3144 KiB
		98	Accepted	17ms	3128 KiB
		99	Accepted	17ms	3124 KiB
		100	Accepted	16ms	3152 KiB
		101	Accepted	16ms	3124 KiB
		102	Accepted	17ms	2980 KiB
		103	Accepted	17ms	2980 KiB
		104	Accepted	16ms	3048 KiB
		105	Accepted	17ms	3000 KiB
		106	Accepted	16ms	3124 KiB
		107	Accepted	16ms	3124 KiB
		108	Accepted	17ms	3124 KiB
		109	Accepted	17ms	3084 KiB
		110	Accepted	17ms	3252 KiB
		111	Accepted	17ms	3232 KiB
		112	Accepted	17ms	3232 KiB
		113	Accepted	17ms	3124 KiB
8	10/10
		114	Accepted	184ms	17484 KiB
		115	Accepted	90ms	9856 KiB
		116	Accepted	87ms	9460 KiB
		117	Accepted	46ms	8904 KiB
		118	Accepted	54ms	6964 KiB
		119	Accepted	54ms	6964 KiB
		120	Accepted	43ms	8464 KiB
		121	Accepted	43ms	8596 KiB
		122	Accepted	43ms	8572 KiB
		123	Accepted	39ms	8312 KiB
		124	Accepted	149ms	17168 KiB
		125	Accepted	158ms	17116 KiB
		126	Accepted	158ms	16904 KiB
		127	Accepted	146ms	16788 KiB
		128	Accepted	59ms	9104 KiB
		129	Accepted	35ms	6080 KiB
		130	Accepted	34ms	5704 KiB
		131	Accepted	23ms	4660 KiB
		132	Accepted	21ms	4636 KiB
		133	Accepted	29ms	7832 KiB
		134	Accepted	32ms	7640 KiB
		135	Accepted	57ms	9256 KiB
		136	Accepted	48ms	8848 KiB
		137	Accepted	43ms	8848 KiB
		138	Accepted	46ms	8752 KiB
		139	Accepted	43ms	8432 KiB
9	15/15
		140	Accepted	847ms	83060 KiB
		141	Accepted	722ms	75384 KiB
		142	Accepted	349ms	66364 KiB
		143	Accepted	375ms	66164 KiB
		144	Accepted	328ms	65892 KiB
		145	Accepted	741ms	51076 KiB
		146	Accepted	277ms	27020 KiB
		147	Accepted	172ms	34600 KiB
		148	Accepted	159ms	34440 KiB
		149	Accepted	189ms	35068 KiB
		150	Accepted	178ms	35332 KiB
		151	Accepted	432ms	35524 KiB
		152	Accepted	759ms	87540 KiB
		153	Accepted	824ms	83468 KiB
		154	Accepted	683ms	81740 KiB
		155	Accepted	377ms	49008 KiB
		156	Accepted	700ms	82776 KiB
		157	Accepted	617ms	82560 KiB
		158	Accepted	620ms	81772 KiB
		159	Accepted	574ms	57976 KiB
		160	Accepted	395ms	45956 KiB
		161	Accepted	574ms	50820 KiB
		162	Accepted	319ms	27020 KiB
		163	Accepted	485ms	45956 KiB
		164	Accepted	639ms	56964 KiB
		165	Accepted	787ms	57476 KiB
		166	Accepted	582ms	79960 KiB
		167	Accepted	514ms	77940 KiB