Problem:


最後の扉

 秘境の地"ナラマンダ地方"

 この奥深い洞窟に眠る黄金の伝説を求め、探検家ボブとマイクは様々な困難に立ち向かいました。ようやくたどり着いた最後の扉。この先には夢に見た黄金が待っています。

 その扉には多数の三角形が描かれていました。試しにマイクがその 1 つに触れてみると、その三角形は光を放ちました。光は三角形の底辺から垂直に頂点方向へ長方形を描きながら伸びていき、その先にある別の三角形に触れました。すると、光に触れた三角形も同じように光を放ち、それを繰り返していきました。

 扉の三角形は全て二等辺三角形(正三角形は含まない)で、どれも同じ大きさで、どれも重ならず（かつ触れることなく）、またどれも光は一定の距離だけ伸びていました。最後の三角形が光り終えると、そこには何事もなかったかのような静けさが戻ってきました。

 ボブは自分の足下に奇妙なメッセージを見つけました。

 「むやみに触れるべからず。汝正しくこの扉に触れたとき、この扉は放たれん。  」

 ボブとマイクはこのメッセージの意味を考えながら、  何度も三角形に触れてみましたがなかなか扉は開きません。 しかし、それを繰り返していくうちに、二人はメッセージの意味がだんだん分かってきました。

 「"むやみに触れるべからず"とは、扉に触れる回数は最小ということ。

  できるだけ少ない回数で触れて、全ての三角形を光らせれば、きっと扉は開くはずだ!」

例えば、扉には図 1 のように複数の二等辺三角形が描かれています。

図 1

 最初に左下の三角形に触れると、図 2 に示すように、その三角形の底辺から垂直に頂点方向へ光が放たれ、その光が触れる三角形が次々に光ります。

図 2

 次に左端の三角形に触れると、図 3 に示すように、全ての三角形が光ります。この手順が全ての三角形を光らせるための最少の手数(2 手)となります。

図 3

  さあ、ボブとマイクが最後の扉を開ける手助けをしよう。

  扉に描かれている三角形の個数、光の伸びる長さ、それぞれの三角形の頂点の座標を入力とし、全ての三角形を光らせるために扉に触れる最少の回数を出力するプログラムを作成して下さい。光の伸びる長さは、底辺からの長さであるものとします。また、光はそれを放つ三角形の頂点を含むような十分な長さを持ちます。

  なお、この問題を解くにあたっては、2 点の距離が 0.01 以下の場合には、同一の点と処理します。また、1 点とひとつの直線の距離が 0.01 以下の場合には、この点はこの直線上にあるとして処理します。

Input

複数のデータセットの並びが入力として与えらる。入力の終わりはゼロふたつの行で示される。各データセットは以下の形式で与えらる。

n d
T1
T2
:
Tn

１行目に扉に描かれている三角形の個数 n (1 ≤ n ≤ 100) と光の伸びる長さを表す整数 d (1 ≤ d ≤ 1000) が与えられる。

続く n 行に各三角形の情報 Ti が以下の形式で与えられる。

x1 y1 x2 y2 x3 y3

三角形の３つの頂点の座標が整数で与えられる(-1000 ≤ x1, y1, x2, y2, x3, y3 ≤ 1000)。

データセットの数は 20 を超えない。

Output

データセットごとに、扉に触れる最少の回数を1行に出力する。

Sample Input

3 4
1 0 3 0 2 1
2 3 2 5 3 4
5 3 5 5 6 4
3 2
1 0 3 0 2 1
2 3 2 5 3 4
5 3 5 5 6 4
0 0

Output for the Sample Input

1
3



Sample input:
3 4
1 0 3 0 2 1
2 3 2 5 3 4
5 3 5 5 6 4
3 2
1 0 3 0 2 1
2 3 2 5 3 4
5 3 5 5 6 4
0 0


Sample output:
1
3

Submission status: Wrong Answer

Solution code:
E = 0.01

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2) * (1 / 2)

def get_base_point(base, point):
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (point[0], point[1], point[2], point[3], point[4], point[5])
  if tmp == b:
    return (point[2], point[3], point[4], point[5], point[0], point[1])
  if tmp == c:
    return (point[4], point[5], point[0], point[1], point[2], point[3])

def touch(x1, y1, x2, y2, x3, y3, x4, y4, d):
  k = -((x2 - x1) * (x1 - x4) + (y1 - y4) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
  #print(k)
  if not (0 <= k <= 1):
    return False
  
  px = x1 + (x2 - x1) * k
  py = y1 + (y2 - y1) * k
  #print(px, py)
  if abs(((px - x4) ** 2 + (py - y4) ** 2) ** (1 / 2)) <= d and (x4 - x1) * (x3 - x1) + (y4 - y1) * (y3 - y1) >= 0:
    return True
  else:
    return False

def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)

while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, point1 in enumerate(points):
    x1, y1, x2, y2, x3, y3 = get_base_point(base, point1)
    #print(x1, y1, x2, y2, x3, y3)
    for j, point2 in enumerate(points):
      if i != j:
        for k in range(3):
          if touch(x1, y1, x2, y2, x3, y3, point2[k * 2], point2[k * 2 + 1], d):
            #print("from", i, "to", j, "is ok.")
            edges[i].append(j)
            break

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
E = 0.01

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2) * (1 / 2)

def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)

def touch(x1, y1, x2, y2, x3, y3, x4, y4, d):
  k = -((x2 - x1) * (x1 - x4) + (y1 - y4) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
  #print(k)
  if not (0 <= k <= 1):
    return False
  
  px = x1 + (x2 - x1) * k
  py = y1 + (y2 - y1) * k
  #print(px, py)
  if abs(((px - x4) ** 2 + (py - y4) ** 2) ** (1 / 2)) + E <= d and (x4 - x1) * (x3 - x1) + (y4 - y1) * (y3 - y1) >= 0:
    return True
  else:
    return False

def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)

while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, point1 in enumerate(points):
    x1, y1, x2, y2, x3, y3 = get_base_point(base, point1)
    #print(x1, y1, x2, y2, x3, y3)
    for j, point2 in enumerate(points):
      if i != j:
        for k in range(3):
          if touch(x1, y1, x2, y2, x3, y3, point2[k * 2], point2[k * 2 + 1], d):
            #print("from", i, "to", j, "is ok.")
            edges[i].append(j)
            break

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
E = 0.01

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2) * (1 / 2)

def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)

def touch(x1, y1, x2, y2, x3, y3, x4, y4, d):
  k = -((x2 - x1) * (x1 - x4) + (y1 - y4) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
  #print(k)
  if not (0 <= k <= 1):
    return False
  
  px = x1 + (x2 - x1) * k
  py = y1 + (y2 - y1) * k
  #print(px, py)
  if abs(((px - x4) ** 2 + (py - y4) ** 2) ** (1 / 2)) + E <= d and (px - x3) * (px - x4) + (py - y3) * (py - y4) >= 0:
    return True
  else:
    return False

def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)

while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, point1 in enumerate(points):
    x1, y1, x2, y2, x3, y3 = get_base_point(base, point1)
    #print(x1, y1, x2, y2, x3, y3)
    for j, point2 in enumerate(points):
      if i != j:
        for k in range(3):
          if touch(x1, y1, x2, y2, x3, y3, point2[k * 2], point2[k * 2 + 1], d):
            #print("from", i, "to", j, "is ok.")
            edges[i].append(j)
            break

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
E = 0.01

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** (1 / 2)

def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)

def touch(x1, y1, x2, y2, x3, y3, x4, y4, d):
  k = -((x2 - x1) * (x1 - x4) + (y1 - y4) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
  #print(k)
  if not (0 <= k <= 1):
    return False
  
  px = x1 + (x2 - x1) * k
  py = y1 + (y2 - y1) * k
  #print(px, py)
  if abs(((px - x4) ** 2 + (py - y4) ** 2) ** (1 / 2)) + E <= d and (px - x3) * (px - x4) + (py - y3) * (py - y4) >= 0:
    return True
  else:
    return False

def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)

while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, point1 in enumerate(points):
    x1, y1, x2, y2, x3, y3 = get_base_point(base, point1)
    #print(x1, y1, x2, y2, x3, y3)
    for j, point2 in enumerate(points):
      if i != j:
        for k in range(3):
          if touch(x1, y1, x2, y2, x3, y3, point2[k * 2], point2[k * 2 + 1], d):
            #print("from", i, "to", j, "is ok.")
            edges[i].append(j)
            break

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
E = 0.01

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2)

def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)

def touch(x1, y1, x2, y2, x3, y3, x4, y4, d):
  k = -((x2 - x1) * (x1 - x4) + (y1 - y4) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
  #print(k)
  if not (0 - E <= k <= 1 + E):
    return False
  
  px = x1 + (x2 - x1) * k
  py = y1 + (y2 - y1) * k
  #print(px, py)
  if ((px - x4) ** 2 + (py - y4) ** 2) ** (1 / 2) <= d + E and (px - x3) * (px - x4) + (py - y3) * (py - y4) >= 0:
    return True
  else:
    return False

def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)

while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, point1 in enumerate(points):
    x1, y1, x2, y2, x3, y3 = get_base_point(base, point1)
    #print(x1, y1, x2, y2, x3, y3)
    for j, point2 in enumerate(points):
      if i != j:
        for k in range(3):
          if touch(x1, y1, x2, y2, x3, y3, point2[k * 2], point2[k * 2 + 1], d):
            #print("from", i, "to", j, "is ok.")
            edges[i].append(j)
            break

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2)


def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)


def cross(point1, point2, point3, point4):
  x1, y1 = point1
  x2, y2 = point2
  x3, y3 = point3
  x4, y4 = point4
  if (y2 - y1) * (x4 - x3) == (x2 - x1) * (y4 - y3):
    return False
  k = ((x1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
 
  if not (0 <= k <= 1):
    return False
 
  x5 = x1 + k * (x2 - x1)
  y5 = y1 + k * (y2 - y1)
  if min(x3, x4) <= x5 <= max(x3, x4) and min(y3, y4) <= y5 <= max(y3, y4):
    return True
  return False


def touch(tr1, tr2, d, base):
  tr1 = get_base_point(base, tr1)
  x1, y1, x2, y2, x3, y3 = tr1
  v12x, v12y = (x2 - x1, y2 - y1)
  v13x, v13y = (x3 - x1, y3 - y1)
  v14x, v14y = v12y * d / (v12x ** 2 + v12y ** 2) ** (1 / 2), -v12x * d / (v12x ** 2 + v12y ** 2) ** (1 / 2)
  if v14x * v13x + v14y * v13y < 0:
    v14x *= -1
    v14y *= -1
  p1 = (x1, y1)
  p2 = (x2, y2)
  p4 = (x1 + v14x, y1 + v14y)
  p5 = (x2 + v14x, y2 + v14y)
  x6, y6, x7, y7, x8, y8 = tr2
  p6 = (x6, y6)
  p7 = (x7, y7)
  p8 = (x8, y8)
  for point1, point2 in combinations((p1, p2, p4, p5), 2):
    for point3, point4 in combinations((p6, p7, p8), 2):
      if cross(point1, point2, point3, point4):
        return True


def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)


while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, tr1 in enumerate(points):
    for j, tr2 in enumerate(points):
      if i != j:
        if touch(tr1, tr2, d, base):
          edges[i].append(j)

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def get_dist(x1, y1, x2, y2):
  return ((x2 - x1) ** 2 + (y2 - y1) ** 2)


def get_base_point(base, point):
  x1, y1, x2, y2, x3, y3 = point
  a = get_dist(x1, y1, x2, y2)
  b = get_dist(x2, y2, x3, y3)
  c = get_dist(x3, y3, x1, y1)
  tmp = min(a, b, c, key=lambda x:abs(x - base))
  if tmp == a:
    return (x1, y1, x2, y2, x3, y3)
  if tmp == b:
    return (x2, y2, x3, y3, x1, y1)
  if tmp == c:
    return (x3, y3, x1, y1, x2, y2)


def cross(point1, point2, point3, point4):
  x1, y1 = point1
  x2, y2 = point2
  x3, y3 = point3
  x4, y4 = point4
  if (y2 - y1) * (x4 - x3) == (x2 - x1) * (y4 - y3):
    return False
  k = ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
 
  if not (0 <= k <= 1):
    return False
 
  x5 = x1 + k * (x2 - x1)
  y5 = y1 + k * (y2 - y1)
  if min(x3, x4) <= x5 <= max(x3, x4) and min(y3, y4) <= y5 <= max(y3, y4):
    return True
  return False


def touch(tr1, tr2, d, base):
  tr1 = get_base_point(base, tr1)
  x1, y1, x2, y2, x3, y3 = tr1
  v12x, v12y = (x2 - x1, y2 - y1)
  v13x, v13y = (x3 - x1, y3 - y1)
  v14x, v14y = v12y * d / (v12x ** 2 + v12y ** 2) ** (1 / 2), -v12x * d / (v12x ** 2 + v12y ** 2) ** (1 / 2)
  if v14x * v13x + v14y * v13y < 0:
    v14x *= -1
    v14y *= -1
  p1 = (x1, y1)
  p2 = (x2, y2)
  p4 = (x1 + v14x, y1 + v14y)
  p5 = (x2 + v14x, y2 + v14y)
  x6, y6, x7, y7, x8, y8 = tr2
  p6 = (x6, y6)
  p7 = (x7, y7)
  p8 = (x8, y8)
  for point1, point2 in combinations((p1, p2, p4, p5), 2):
    for point3, point4 in combinations((p6, p7, p8), 2):
      if cross(point1, point2, point3, point4):
        return True


def bfs(i, visited, edges, order):
  visited[i] = True
  for to in edges[i]:
    if not visited[to]:
      bfs(to, visited, edges, order)
  order.append(i)


while True:
  n, d = map(int, input().split())
  if n == 0:
    break
  points = [list(map(int, input().split())) for _ in range(n)]
  
  point = points[0]
  a = get_dist(point[0], point[1], point[2], point[3])
  b = get_dist(point[2], point[3], point[4], point[5])
  c = get_dist(point[4], point[5], point[0], point[1])
  base = -1
  if [a, b, c].count(a) == 1:
    base = a
  else:  
    base = b
  #print(base)
  
  edges = [[] for _ in range(n)]
  for i, tr1 in enumerate(points):
    for j, tr2 in enumerate(points):
      if i != j:
        if touch(tr1, tr2, d, base):
          edges[i].append(j)

  order = []
  visited = [False] * n
  for i in range(n):
    if not visited[i]:
      bfs(i, visited, edges, order)
  order.reverse()
  

  visited = [False] * n
  lst = []
  cnt = 0
  for i in order:
    if not visited[i]:
      cnt += 1
      bfs(i, visited, edges, lst)
  print(cnt)