P16936 [HackerEarth] Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the g
普及-
题目描述

Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the graph.

A critical link in a graph is an edge that has the following property: If we cut the link/edge, the graph will have exactly one more connected component than it previously had, and the difference between the number of nodes on each side of the edge is less than a certain integer P.

Given P and the graph, can you help Rhezo calculate the number of critical links?

Input:

First line contains 3 integers N, M and P as described in the problem statement. Each of the next M lines contain 2 integers A and B, meaning that node number A has a link/edge with node number B.

Output:

Find the number of critical links in the graph.

Constraints:

1 ≤ N, M, P ≤ 10^{5}

1 ≤ A,B ≤ N

1 ≤ M ≤ $max(10^{5},N \cdot (N-1) / 2)$

SAMPLE INPUT
5 4 100
1 2
2 3
3 4
4 5

SAMPLE OUTPUT
4

Explanation

Each edge is a critical link.

输入格式

见题面

输出格式

见题面

样例输入
500 603 309 29 271 169 464 261 373 226 228 307 91 183 259 115 251 188 69 402 124 174 270 463 171 102 86 51 15 105 341 66 106 249 94 377 418 409 137 290 135 216 448 77 398 206 44 500 245 112 253 368 285 374 183 455 476 268 5 342 224 197 408 182 446 353 58 215 262 46 356 248 261 303 176 10 361 219 361 105 330 114 473 115 487 7 421 314 274 426 156 350 474 63 31 419 267 440 133 380 337 340 127 97 143 155 458 355 373 318 459 203 283 283 169 270 289 89 83 415 366 90 116 340 152 146 110 419 85 243 298 421 434 277 369 76 431 178 282 155 495 241 357 278 375 377 399 16 466 333 282 183 423 397 374 74 42 484 344 478 78 494 250 11 122 118 439 404 295 220 58 141 460 267 270 187 495 20 202 312 353 335 495 275 231 368 200 124 351 44 101 428 389 350 439 362 319 377 265 465 96 174 105 408 292 227 446 287 246 147 98 98 481 444 372 63 312 72 186 14 467 138 294 207 487 84 68 157 312 184 121 259 357 77 166 1 303 463 287 401 461 236 498 293 180 222 355 343 145 40 356 463 29 149 169 367 84 88 23 395 271 143 154 479 220 171 479 374 134 117 274 94 353 124 387 32 197 93 374 193 133 81 155 13 230 175 380 165 114 402 60 384 397 213 214 116 235 45 341 368 161 115 314 13 238 52 44 286 144 269 478 128 350 132 141 431 158 20 95 271 273 154 6 169 218 219 136 453 115 477 172 276 91 485 288 180 36 184 465 32 452 442 159 301 425 299 231 434 170 178 204 443 331 61 111 401 131 99 353 246 75 376 21 165 361 308 196 248 343 12 131 295 305 290 447 81 440 30 14 110 207 217 52 389 277 14 289 407 112 493 4 38 369 24 202 81 184 249 180 26 112 311 172 416 452 119 496 391 148 9 500 206 77 403 94 205 269 235 464 232 227 467 270 447 491 323 27 26 72 59 51 183 369 75 451 320 193 298 210 192 307 62 397 235 316 342 292 84 428 255 316 155 73 437 453 415 259 332 440 182 390 343 217 110 417 167 429 109 316 490 152 122 403 400 209 219 241 500 302 169 254 469 175 326 257 479 241 16 310 32 49 199 374 265 308 142 283 88 250 99 430 253 72 332 152 280 50 245 131 204 265 236 24 291 414 281 269 6 296 79 37 196 129 263 461 289 404 95 376 6 193 305 258 117 137 262 248 38 6 379 241 270 466 117 60 379 397 180 384 44 110 273 239 239 35 51 27 290 146 254 295 190 411 405 306 399 166 54 436 23 284 29 144 249 145 55 480 393 234 363 436 344 487 174 434 21 225 312 163 222 417 309 411 327 213 69 225 230 474 161 252 257 41 247 357 185 301 336 429 387 51 364 230 37 389 15 410 465 178 94 380 449 421 445 17 497 174 490 9 278 98 49 24 454 85 177 142 13 63 192 228 144 228 117 158 489 81 335 60 267 280 292 215 200 236 83 49 409 72 57 38 21 106 414 474 42 90 467 407 152 158 134 147 238 250 304 226 331 490 286 449 269 429 15 321 164 97 221 424 20 277 462 40 234 227 365 276 168 332 182 171 341 167 317 78 417 120 304 99 461 441 399 81 369 413 253 384 361 473 307 232 102 120 271 335 346 487 462 13 318 495 35 159 162 351 88 78 322 391 28 282 183 426 215 403 338 319 286 50 292 93 281 393 212 403 79 410 389 41 274 207 35 309 217 196 159 304 125 333 47 152 466 229 77 180 484 266 499 269 315 142 361 447 386 425 349 464 186 238 356 311 296 391 119 364 438 130 19 63 314 65 66 279 146 143 459 129 260 309 397 427 302 110 373 39 386 222 2 423 311 358 233 458 100 204 321 37 185 339 451 498 256 17 276 401 11 86 381 270 246 129 196 47 238 421 85 475 494 439 397 304 148 130 113 247 185 285 135 369 475 86 366 230 102 141 482 112 79 214 233 324 343 429 371 432 201 307 407 194 245 155 349 244 136 461 490 320 245 125 188 71 210 405 301 163 398 134 274 476 348 358 299 190 138 21 121 338 180 379 31 424 34 379 20 21 191 9 341 287 485 380 358 194 137 10 208 34 143 333 361 342 191 11 383 328 32 356 166 63 234 196 338 119 427 357 140 117 366 332 404 350 63 261 396 199 270 455 84 264 288 444 106 478 307 488 305 190 195 470 252 429 18 89 399 296 446 390 412 311 221 315 12 136 427 259 334 48 214 270 213 269 330 371 108 486 60 303 308 311 83 177 400 481 472 345 223 383 7 295 50 370 430 328 481 116 376 46 385 39 398 449 307 79 320 266 64 379 420 371 190 2 47 441 335 370 285 57 253 143 351 154 364 133 481 344 248 356 241 132 394 138 432 52 68 251 170 132 482 89 354 171 443 253 111 129 122 247 185 226 241 387 379 104 19 360 300 118 67 40 249 313 30 33 216 97 283 385 80 264 326 286 286 120 390 248 248 363 346 284 89 438 170 319 42 41 178 193 10 97 84 111 409 465 143 476 414 425 213 345 41 38 130 326 157 19 426 404 382 271 187 322 209 208 140 102 100 170 266 229 46 214 353 459 490 65 303 30 454 285 208 110 155 133 365 388 255 403 209 315 463 201 268 414 370 413 375 487 494 446 12 39 159 364 349 149 429 3 30 382 287 237 344 442 221 60 329 328 315 390 142 277 90 262 42 459 26 417 445 19 362 308 409 21 23 109 21 303 112 50
样例输出
80