


'''simple docstring'''





from collections import deque


def 					a__    (				UpperCamelCase_	:			List[str]	):
   return input(UpperCamelCase_	).strip().split(''' '''	)


def 					a__    (				UpperCamelCase_	:			int,      UpperCamelCase_	:			int	):
   UpperCAmelCase__  :dict[int, list[int]]            =			{}
   for i in range(UpperCamelCase_	):
      UpperCAmelCase__  :Dict            =			[]

   for e in range(UpperCamelCase_	):
      UpperCAmelCase__      ,	UpperCAmelCase__  :int            =			(int(UpperCamelCase_	) for i in _input(F'''Edge {e + 1}: <node1> <node2> '''	))
      graph[x].append(UpperCamelCase_	)
   return graph


def 					a__    (				UpperCamelCase_	:			int,      UpperCamelCase_	:			int	):
   UpperCAmelCase__  :dict[int, list[int]]            =			{}
   for i in range(UpperCamelCase_	):
      UpperCAmelCase__  :Optional[int]            =			[]

   for e in range(UpperCamelCase_	):
      UpperCAmelCase__      ,	UpperCAmelCase__  :Optional[Any]            =			(int(UpperCamelCase_	) for i in _input(F'''Edge {e + 1}: <node1> <node2> '''	))
      graph[x].append(UpperCamelCase_	)
      graph[y].append(UpperCamelCase_	)
   return graph


def 					a__    (				UpperCamelCase_	:			int,      UpperCamelCase_	:			int	):
   UpperCAmelCase__  :dict[int, list[tuple[int, int]]]            =			{}
   for i in range(UpperCamelCase_	):
      UpperCAmelCase__  :Optional[int]            =			[]

   for e in range(UpperCamelCase_	):
      UpperCAmelCase__      ,	UpperCAmelCase__      ,	UpperCAmelCase__  :str            =			(int(UpperCamelCase_	) for i in _input(F'''Edge {e + 1}: <node1> <node2> <weight> '''	))
      graph[x].append((y, w)	)
      graph[y].append((x, w)	)
   return graph


if __name__ == "__main__":
    __lowerCamelCase				,		__lowerCamelCase       				=	(int(i) for i in _input('''Number of nodes and edges: '''))

    __lowerCamelCase       				=	int(
        _input(
            '''Press 1 or 2 or 3 \n'''
            '''1. Unweighted directed \n'''
            '''2. Unweighted undirected \n'''
            '''3. Weighted undirected \n'''
        )[0]
    )

    __lowerCamelCase       				=	{
        1: initialize_unweighted_directed_graph,
        2: initialize_unweighted_undirected_graph,
        3: initialize_weighted_undirected_graph,
    }[graph_choice](n, m)


def 					a__    (				UpperCamelCase_	:			Dict,      UpperCamelCase_	:			List[str]	):
   UpperCAmelCase__      ,	UpperCAmelCase__  :str            =			{s}, [s]
   print(UpperCamelCase_	)
   while _s:
      UpperCAmelCase__  :str            =			0
      for i in g[_s[-1]]:
         if i not in vis:
            _s.append(UpperCamelCase_	)
            vis.add(UpperCamelCase_	)
            UpperCAmelCase__  :List[str]            =			1
            print(UpperCamelCase_	)
            break
      if not flag:
         _s.pop()


def 					a__    (				UpperCamelCase_	:			Tuple,      UpperCamelCase_	:			Dict	):
   UpperCAmelCase__      ,	UpperCAmelCase__  :Dict            =			{s}, deque([s]	)
   print(UpperCamelCase_	)
   while q:
      UpperCAmelCase__  :Union[str, Any]            =			q.popleft()
      for v in g[u]:
         if v not in vis:
            vis.add(UpperCamelCase_	)
            q.append(UpperCamelCase_	)
            print(UpperCamelCase_	)


def 					a__    (				UpperCamelCase_	:			str,      UpperCamelCase_	:			Tuple	):
   UpperCAmelCase__      ,	UpperCAmelCase__      ,	UpperCAmelCase__  :str            =			{s: 0}, set(), {s: 0}
   while True:
      if len(UpperCamelCase_	) == len(UpperCamelCase_	) - 1:
         break
      UpperCAmelCase__  :str            =			100_000
      for i in dist:
         if i not in known and dist[i] < mini:
            UpperCAmelCase__  :Union[str, Any]            =			dist[i]
            UpperCAmelCase__  :Optional[int]            =			i
      known.add(UpperCamelCase_	)
      for v in g[u]:
         if v[0] not in known and dist[u] + v[1] < dist.get(v[0],      100_000	):
            UpperCAmelCase__  :List[Any]            =			dist[u] + v[1]
            UpperCAmelCase__  :Optional[Any]            =			u
   for i in dist:
      if i != s:
         print(dist[i]	)


def 					a__    (				UpperCamelCase_	:			str,      UpperCamelCase_	:			List[Any]=None,      UpperCamelCase_	:			List[str]=None	):
   if q is None:
      UpperCAmelCase__  :Dict            =			[1]
   if ind is None:
      UpperCAmelCase__  :Tuple            =			[0] * (len(UpperCamelCase_	) + 1)  # SInce oth Index is ignored
      for u in g:
         for v in g[u]:
            ind[v] += 1
      UpperCAmelCase__  :Union[str, Any]            =			deque()
      for i in g:
         if ind[i] == 0:
            q.append(UpperCamelCase_	)
   if len(UpperCamelCase_	) == 0:
      return
   UpperCAmelCase__  :List[Any]            =			q.popleft()
   print(UpperCamelCase_	)
   for w in g[v]:
      ind[w] -= 1
      if ind[w] == 0:
         q.append(UpperCamelCase_	)
   topo(UpperCamelCase_,      UpperCamelCase_,      UpperCamelCase_	)


def 					a__    (				):
   UpperCAmelCase__  :Any            =			input().strip()
   UpperCAmelCase__  :Optional[Any]            =			[]
   for _ in range(UpperCamelCase_	):
      a.append(map(UpperCamelCase_,      input().strip().split()	)	)
   return a, n


def 					a__    (				UpperCamelCase_	:			Dict	):
   ((UpperCAmelCase__)      ,	(UpperCAmelCase__))  :List[Any]            =			a_and_n
   UpperCAmelCase__  :Tuple            =			list(UpperCamelCase_	)
   UpperCAmelCase__  :Any            =			[[0] * n for i in range(UpperCamelCase_	)]
   for k in range(UpperCamelCase_	):
      for i in range(UpperCamelCase_	):
         for j in range(UpperCamelCase_	):
            if dist[i][j] > dist[i][k] + dist[k][j]:
               UpperCAmelCase__  :List[str]            =			dist[i][k] + dist[k][j]
               UpperCAmelCase__  :str            =			k
   print(UpperCamelCase_	)


def 					a__    (				UpperCamelCase_	:			Tuple,      UpperCamelCase_	:			Optional[Any]	):
   UpperCAmelCase__      ,	UpperCAmelCase__      ,	UpperCAmelCase__  :Any            =			{s: 0}, set(), {s: 0}
   while True:
      if len(UpperCamelCase_	) == len(UpperCamelCase_	) - 1:
         break
      UpperCAmelCase__  :Any            =			100_000
      for i in dist:
         if i not in known and dist[i] < mini:
            UpperCAmelCase__  :str            =			dist[i]
            UpperCAmelCase__  :Any            =			i
      known.add(UpperCamelCase_	)
      for v in g[u]:
         if v[0] not in known and v[1] < dist.get(v[0],      100_000	):
            UpperCAmelCase__  :Optional[int]            =			v[1]
            UpperCAmelCase__  :Tuple            =			u
   return dist


def 					a__    (				):
   UpperCAmelCase__      ,	UpperCAmelCase__  :Optional[Any]            =			map(UpperCamelCase_,      input().split(''' '''	)	)
   UpperCAmelCase__  :int            =			[]
   for _ in range(UpperCamelCase_	):
      edges.append(map(UpperCamelCase_,      input().split(''' '''	)	)	)
   return edges, n


def 					a__    (				UpperCamelCase_	:			List[Any]	):
   # Sort edges on the basis of distance
   ((UpperCAmelCase__)      ,	(UpperCAmelCase__))  :Dict            =			e_and_n
   e.sort(reverse=UpperCamelCase_,      key=lambda UpperCamelCase_	: x[2]	)
   UpperCAmelCase__  :str            =			[{i} for i in range(1,      n + 1	)]
   while True:
      if len(UpperCamelCase_	) == 1:
         break
      print(UpperCamelCase_	)
      UpperCAmelCase__  :str            =			e.pop()
      for i in range(len(UpperCamelCase_	)	):
         if x[0] in s[i]:
            break
      for j in range(len(UpperCamelCase_	)	):
         if x[1] in s[j]:
            if i == j:
               break
            s[j].update(s[i]	)
            s.pop(UpperCamelCase_	)
            break


def 					a__    (				UpperCamelCase_	:			Union[str, Any]	):
   UpperCAmelCase__  :int            =			[]
   for node in graph:
      if not graph[node]:
         isolated.append(UpperCamelCase_	)
   return isolated







'''simple docstring'''





def 					a__    (				UpperCamelCase_	:			int	):
   UpperCAmelCase__  :str            =			[True for i in range(n + 1	)]
   UpperCAmelCase__  :List[str]            =			[i - 1 for i in range(n + 1	)]
   UpperCAmelCase__  :str            =			[]
   for i in range(2,      n + 1	):
      if is_prime[i]:
         primes.append(UpperCamelCase_	)
      for j in range(0,      len(UpperCamelCase_	)	):
         if i * primes[j] >= n:
            break
         UpperCAmelCase__  :List[str]            =			False

         if i % primes[j] == 0:
            UpperCAmelCase__  :Any            =			totients[i] * primes[j]
            break

         UpperCAmelCase__  :str            =			totients[i] * (primes[j] - 1)

   return totients


if __name__ == "__main__":
    import doctest

    doctest.testmod()



