#DFS - 인접 리스트
def dfs(graph, v,vi,r):
  #global r
  r.append(v)
  for i in range(len(graph[v])):
    if(vi[graph[v][i]]==False):
      vi[graph[v][i]]=True
      dfs(graph,graph[v][i],vi,r)

r=[]
graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

vi=[False]*9
vi[1]=True
dfs(graph, 1,vi,r)
#print(1, end=" ")
print(r)

#include <bits/stdc++.h>
using namespace std;
//1337 : 달팽이삼각형
int main()
{
    int a[100][100] = {0,},n,x = 0,y = 0,cnt = 0;

    cin >> n;
    fill(&a[0][0], &a[99][100], -1);

    for(;;){
        for(int i = 0;i < n;i++){
            if(cnt == 10){
                cnt = 0;
            }
            a[x][y] = cnt++;
            x++;
            y++;
        }
        n--;
        for(int i  = 0;i < n;i++){
            if(cnt == 10){
                cnt = 0;
            }
            y--;
            a[x][y] = cnt++;
        }
        n--;
        for(int i = 0;i < n;i++){
            if(cnt == 10){
                cnt = 0;
            }
            x--;
            a[x][y] = cnt++;
        }
        x++;
        y++;
        if(a[x][y] != -1){
            break;
        }

    }
    for(int i = 0;i < 20;i++){
        for(int j = 0;j < 20;j++){
            //if(a[i][j] != 0){
                printf("%3d",a[i][j]);//cout <<  << " ";
            //}
        }
        cout << "\n";
    }
    return 0;
}

# include <stdio.h>
//2071 : 파스칼 삼각형
int main()
{
   int i,j,n,m;
   int a[50][50];

   scanf("%d %d",&n,&m);

   for(i=0;i<n;i++)
   {
      for(j=0;j<n;j++)
         a[i][j]=1;
   }

   for(i=2;i<n;i++)
   {
      for(j=1;j<i;j++)
      {
         a[i][j]=a[i-1][j]+a[i-1][j-1];
      }
   }

   if(m==1)
   {
      for(i=0;i<n;i++)
      {
         for(j=0;j<=i;j++)
         {
            printf("%d ",a[i][j]);
         }
         printf("\n");
      }
   }
   else if(m==2)
   {
      for(i=n-1;i>=0;i--)
      {
         for(j=0;j<n-i-1;j++)
         {
            printf(" ");
         }
         for(j=i;j>=0;j--)
         {
            printf("%d ",a[i][j]);
         }
         printf("\n");
      }
   }
   else if(m==3)
   {
      for(i=0;i<n;i++)
      {
         for(j=n-1;j>=n-i-1;j--)
         {
            printf("%d ",a[j][n-i-1]);
         }
         printf("\n");
      }
   }
   return 0;
}

# include <stdio.h>
//1337 : 달팽이삼각형
int main()
{
    int n,m,i,j,count=0,a[50][50],x=-1,y=-1;

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        for(j=i;j<n;j++)
        {
            if(i%3==0)
            {
                x++;
                y++;
            }
            else if(i%3==1)
            {
                y--;
            }
            else if(i%3==2)
            {
                x--;
            }
            a[x][y] = (count++)%10;
        }
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<=i;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

#시각
n=int(input())
t=0
for i in range(n+1):
  for j in range(60):
    for k in range(60):
      s = str(i) + str(j) + str(k)
      if '3' in s:
        t += 1
print(t)

#왕실의 나이트 
a = input()
r = int(a[1])
z=0
col = int(ord(a[0])) - int(ord('a')) + 1
x=[1,2,-1,-2]
y=[2,1,-2,-1]
for i in range(4):
    for j in range(2):
        if(col+x[i]<9 and col+x[i]>0 and r+y[(i%2)+(j*2)]>0 and r+y[(i%2)+(j*2)]<9):
            z=z-1
        z=z+1
print(8-z)

#게임개발 
n, m=map(int, input().split())
x, y, d=map(int, input().split())
check=0
v = [[0]*m for _ in range(n)]
v[x][y]=1
dx=[-1,0,1,0]
dy=[0,1,0,-1]
cnt=0
array = []
for i in range(n):
  temp = list(map(int, input().split()))
  array.append(temp)
while True:
  if(array[x+dx[(d+3)%4]][y+dy[(d+3)%4]]==0):
    if(v[x+dx[(d+3)%4]][y+dy[(d+3)%4]]==0):
      x=x+dx[(d+3)%4]
      y=y+dy[(d+3)%4]
      v[x][y]=1
      d=(d+3)%4
      check=0
      continue
    #d=(d+3)%4
    #check=check+1
    #continue 
  d=(d+3)%4
  check=check+1
  #continue
  if(check==4):
    if(array[x+dx[(d+2)%4]][y+dy[(d+2)%4]]==1):
      break
    else:
      x=x+dx[(d+2)%4]
      y=y+dy[(d+2)%4]
      check=0
for i in range(m):
  for j in range(n):
    if(1 == v[i][j]):
      cnt=cnt+1
print(cnt)

#stack
stack = []
stack.append(5)
stack.append(4)
stack.append(6)

print(stack)

x = stack.pop()
print(x, stack)

#queue
from collections import deque
queue = deque()

queue.append(6)
queue.append(8)
queue.append(3)
queue.append(5)

print(queue)

x=queue.pop()
print(x,queue)

x=queue.popleft()
print(x,queue)

#선택정렬
a=[3,4,2,1,5,6,7,2]
print(a)
mint=100
k=0
temp=0
for i in range(len(a)):
  for j in range(i,len(a)):
    if(mint>a[j]):
      mint=a[j]
      k=j
  a[i], a[k] = a[k], a[i]
  mint=100
print(a)

#선택정렬
a=[3,4,2,1,5,6,7,2]
print(a)
mint=100
k=0
temp=0
for i in range(len(a)):
  for j in range(i,len(a)):
    if(mint>a[j]):
      mint=a[j]
      k=j
  temp=a[i]
  a[i]=mint
  a[k]=temp
  mint=100
print(a)

#include <bits/stdc++.h>
using namespace std;
//1329 : 별삼각형3
int main()
{
    int n;
    cin >> n;

    int s=0;
    int e=0;

    char m[100][100]={0,};

    for(int i=0; i<n; i++){
        //space
        for(int j=s;j<=e;j++){
            m[i][j]='*';
        }

        cout << s << "," << e << "\n";

        if(i>n/2-1){
            s--;
            e=e-3;
        }
        else{
            s++;
            e=e+3;
        }

        //printf("  \n");
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n*3; j++){
            cout << m[i][j];
        }
        cout << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//숫자카드 게임
int main()
{
    int n,b;
    int a[100][100];

    cin >> n >> b;

    int min = 500;
    int max=-500;
    for(int i=0; i<n; i++){
        for(int j=0; j<b; j++){
            cin >> a[i][j];
            if(min > a[i][j]){
                min = a[i][j];
            }
        }
        if(max<min){
            max= min;
        }
        min=500;
    }

    cout << max;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//1641 : 숫자삼각형
int main()
{
    int a=1;
    int n;
    cin >>n;

    int x[100][100]={0,};

    for(int i=0; i<n; i++){
        if(i%2!=0){
            for(int j=i; j>-1; j--){
                x[i][j]=a++;
            }

        }
        else{
            for(int j=0; j<=i; j++){
                x[i][j]=a++;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(x[i][j] != 0){
                cout << x[i][j];
            }

        }
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h> 
using namespace std; 
//상하좌우 
int main() 
{ 
    int n; 
    cin >> n; 

    int x=1,b=1; 

    char a[5]; 
    for(int i=0; i<6; i++){ 
        cin >> a[i]; 
        if(a[i]=='R'){ 
           if(b+1<=n){ 
                b++; 
           } 
        } 
        else if(a[i]=='L'){ 
           if(b-1>0){ 
                b--; 
           } 
        } 
        else if(a[i]=='D'){ 
           if(x+1<=n){ 
                x++; 
           } 
        } 
        else if(a[i]== 'U'){ 
           if(x-1>0){ 
                x--; 
           } 
        } 
    } 

    cout << x << "  " << b; 

    return 0; 
}

#include <bits/stdc++.h>
using namespace std;
//숫자삼각형 (종류2)
int main()
{
    int n;
    cin >> n;
    int x;
    //cin >>x;
    int o = 0;
    int a[100][100] = {0,};

    fill(&a[0][0], &a[99][100], -1);

    //if(x==2){

    int q=2*n-1;
    int p=0;
    for(int i=0; i<n; i++){
        for(int j=p; j<q; j++){
            a[i][j]=o;
        }
        o++;
        q = q - 1;
        p = p+1;
    }
    //}

    for(int i=0; i<n; i++){
        for(int j=0; j<2*n-1; j++){
            if(a[i][j] == -1){
                cout << " ";
            }
            else{
                cout << a[i][j];
            }

        }
        cout << "\n";
    }


    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//배열초기화 fill (1차원 배열)
int main()
{
    int a[5];
    //fill(&a[0], &a[5], 9);
    fill(a, a+5, 89);

    for(int i=0; i<5; i++){
        printf("=%d", a[i]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//배열초기화 fill (2차원 배열)
int main()
{
    int a[5][5];
    fill(&a[0][0], &a[4][5], 77);
    //fill(a, a+5, 89);

    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            printf("=%d", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//배열초기화 fill (2차원 배열)
int main()
{
    int a[5][5];
    fill(&a[0][0], &a[4][5], 77);
    //fill(a, a+5, 89);

    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            printf("=%d", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//숫자삼각형 (종류3)
int main()
{
    int n;
    cin >> n;
    int x;

    int a[100][100];
    fill(&a[0][0], &a[99][100], -1);


    int p = 1;
    for(int i=0; i<2*n-1; i++){
        for(int j=0; j<p; j++){
            a[i][j] = j+1;
        }
        if(i<n/2){
            p++;
        }
        else{
            p--;
        }
    }

    for(int i=0; i<2*n; i++){
        for(int j=0; j<n; j++){
            if(a[i][j] == -1){
                cout << " ";
            }
            else{
                cout << a[i][j];
            }

        }
        cout << "\n";
    }
    return 0;
}

#반복제어문2 - 자가진단5
a=list(map(int, input().split()))
c=0
d=0
t=0
for i in a:
  if i%3==0:
    c+=1
  if i%5==0:
    d+=1
print("Multiples of 3 : %d" %c)
print("Multiples of 5 : %d" %d)​

#반복제어문2 - 자가진단7
for i in range(2, 7):
  for j in range(i, i+5):
    print(j, end=" ")
  print(" ")​

#반복제어문2 - 자가진단6
k=int(input())
a=list(map(int, input().split()))
su=0
for i in a:
  su+=i
print("avg : %.1f" %(su/k))
if(su/k>=80):
  print("pass")
else:
  print("fail")

#반복제어문2 - 자가진단8
a, b=map(int, input().split())

if a>b:
  for i in range(1, 10):
    for j in range(a, b-1, -1):
      print("%d * %d =  %d   " %(j,i,i*j), end=" ")
    print(" ")
else:
  for i in range(1, 10):
    for j in range(a, b+1):
      print("%d * %d =  %d   " %(j,i,i*j), end=" ")
    print(" ")​

#반복제어문2 - 자가진단8
for i in range(2, 5):
  for j in range(1, 6):
    print("%d * %d =  %d   " %(i,j,i*j), end=" ")
  print(" ")

#반복제어문2 - 형성평가8
a, b=map(int, input().split())
for i in range(1, a+1):
  for j in range(1, b+1):
    print(i*j, end=" ")
  print(" ")

#반복제어문3 - 자가진단1
n=int(input())
su=0
i=1
while True:
  su+=i
  if su>=n:
    print("%d %d %d" %(i, i//2+1, su))
    break
  i+=2​

#반복제어문3 - 자가진단3

n=int(input())
for i in range(1, n+1):
  for j in range(n-i+1, 0, -1):
    print("*",end="")
  print(" ")
for i in range(1, n+1):
  for j in range(1, i+1):
    print("*",end="")
  print(" ")​

#반복제어문3 - 자가진단2
n=int(input())
for i in range(1, n+1):
  for j in range(1, i+1):
    print("*",end="")
  print(" ")

#554 : 반복제어문3 - 자가진단7
n=int(input())
ai="A"
k=1
for i in range(1, n+1):
  for _ in range(n-i+1):
    print(k, end=" ")
    k+=1
  for _ in range(i):
    print(ai, end=" ")
    ai=chr(ord(ai)+1)
  print("")​

#143 : 반복제어문3 - 형성평가4
n=int(input())
for i in range(n*2-1, -1, -2):
  for j in range((n*2-1-i)//2):
    print(" ",end="")
  for k in range(i):
    print("*",end="")
  print("")
for i in range(3, n*2+1, 2):
  for j in range((n-i+2)//2):
    print(" ",end="")
  for k in range(i):
    print("*",end="")
  print("")

#141 : 반복제어문3 - 형성평가2
n=int(input())
for i in range(1, 101):
  if((n*i)%10==0):
    print(n*i, end=" ")
    break
  else:
    print(n*i, end=" ")​

#142 : 반복제어문3 - 형성평가3
n=int(input())
for i in range(1, n+1):
  for _ in range(i):
    print("*",end="")
  print("")
for i in range(1, n):
  for _ in range(n-i):
    print("*",end="")
  print("")

#140 : 반복제어문3 - 형성평가1
n=list(map(int,input().split()))
sum1=0
ti=0
for i in n:
  if(i==0):
    break
  if(ti==20):
    break
  else:
    sum1+=i
  ti+=1
print("%d %d" %(sum1, sum1//ti))

#140 : 반복제어문3 - 형성평가1
n=list(map(int,input().split()))
sum1=0
#ti=0
for ti, i in enumerate(n):
  print(ti, i)
  if(i==0):
    break
  if(ti==20):
    break
  else:
    sum1+=i
  #ti+=1
print("%d %d" %(sum1, sum1//ti))

#553 : 반복제어문3 - 자가진단6
n=int(input())
al="A"
for i in range(n):
  for j in range(n-i,0,-1):
    print(al,end="")
    al=chr(ord(al)+1)
  print(" ")

#반복제어문3 - 자가진단4

n=int(input())
for i in range(1, n+1):
  for k in range(0, i-1):
    print(" ",end="")
  for j in range(n-i+1, 0, -1):
    print("*",end="")
  print(" ")

n, m, k = map(int, input().split())
c=list(map(int, input().split()))
p=max(c)
s=c.count(p)
if(s>1):
  print(m*p)
else:
  c.remove(p)
  q=max(c)
  a=m//(k+1)
  b=m%(k+1)
  print(a*(p*k+q)+p*b)

#include <bits/stdc++.h>
using namespace std;
//큰수의 법칙

int main()
{
    int n;
    cin >> n;

    int k,m;
    cin >> m >> k;

    int max = -3200;
    int smax;
    int a[100];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    //////////////
    //sort -> max, smax구하자
    sort(a,a+n);
    max = a[n-1];
    smax = a[n-2];


    //////////////
    int cnt=0;
    int ans=0;

    for(int i=0; i<100; i++){
        if(cnt < m){
            if(i<k){
                ans= ans+max;
                cnt++;
            }
            else{
                cout << i << " = i \n";
                ans= ans+smax;
                cnt++;
                i=0;
            }
        }
        else{
            break;
        }
    }
    cout << cnt << " = cnt \n";
    cout << ans;
    
    return 0;
}

**간접 의문문?

: 직접 물어보는 것이 아니라 간접적으로 질문 하는 방법.

  의문문이 문장의 일부가 되어 사용하는것.

  의문문이 명사절 자리에 쓰여 주로 목적어 역할을 함.

순서는 의문사 + 주어 + 동사 의 어순을 가진다.

* be동사/조동사 가 들어간 간접의문문 - 의문사 + 주어 + be동사/조동사

Can you tell me? + Where is the post office?
→ Can you tell me where the post office?

Do you know? + Where is he going?
→ Do you know where he is going?

Did you know? + Who is Sally?
→ Did you know who Sally is?

Do you know? + What should we do?
→ Do you know what we should do?

* 일반동사가 있는 간접 의문문 - 의문사 + 주어 + 일반동사

Do you know? + When did he pass the exam?
→Do you know when he passed the exam.

Could you tell me? + How do I get to the station?
→Could you tell me how I get to the station.

Does anyone know? + Who helped her?
→Does anyone know who helped her?

* 의문사가 없는 경우 - if[whether] + 주어 + 동사

He doesn't know. + Does she like him?
→ He doesn't know if[whether] she likes him.

I wonder. + Did Your friend buy a new car?
→ I wonder if[whether] your friend bought a new car.

please tell me. + Can she swim?
→Please tell me if[whether] she can swim.

* 생각동사가 들어간 간접의문문 -  의문사 + 주절 + 주어 + 동사
주절에 think, believe, suppose, guess 와 같은 생각에 관련된 동사들이 나왔을 경우 
의문사는 문장의 맨 앞에 위치한다. (can you guess는 예외)

Do you think? + What is your brother doing now?
→ What do you think your brother doing now?

Do you suppose? + When will the computer be repaired?
→ When do you suppose the computer will be repaired?

Do you believe? + Who broke the window?
→ Who do you believe broke the window?

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2079&sca=2040

import math
def is_prime_number(x):
  for i in range(2, int(math.sqrt(x))+1):
    if x%i == 0:
      return False
  return True

n, m = map(int, input().split())
cnt = 0

for a in range(n, m+1):
  if is_prime_number(a):
    cnt += 1

print(cnt)

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1174&sca=2040

import math
def is_prime_number(x):
  for i in range(2, int(math.sqrt(x))+1):
    if x%i == 0:
      return False
  return True

m = int(input())

for _ in range(0,m):
  i = int(input())
  u = i+1
  d = i-1
  while True:
    flag = False
    p = ""
    if is_prime_number(d):
      flag = True
      p += str(d) + " "
      #print(d)

    if is_prime_number(u):
      flag = True
      p += str(u) + " "
      #print(u)
    

    if flag == True:
      print(p)
      break
    
    u+=1
    d-=1
  

m = int(input())
n = int(input())
sum = 0
tmin = 100000
for a in range(m, n+1):
  cnt = 0
  for i in range(1, a):
    if a%i == 0:
      cnt += 1
  if cnt == 1:
    sum += a
    if tmin >  a:
      tmin = a
print("%d\n%d" %(sum, tmin))

def is_prime_number(x):
  for i in range(2, x):
    if x%i == 0:
      return False
  return True

m = int(input())
n = int(input())
sum = 0
tmin = 100000
for a in range(m, n+1):
  if(is_prime_number(a)):
    sum += a
    if tmin >  a:
      tmin = a
print("%d\n%d" %(sum, tmin))

import math
def is_prime_number(x):
  for i in range(2, int(math.sqrt(x))+1):
    if x%i == 0:
      return False
  return True

m = int(input())
n = int(input())
sum = 0
tmin = 100000
for a in range(m, n+1):
  if(is_prime_number(a)):
    sum += a
    if tmin >  a:
      tmin = a
print("%d\n%d" %(sum, tmin))

555 : 배열1 - 자가진단1

li = list(input().split())
print(li)
for i in li:
  print(i, end="")

556 : 배열1 - 자가진단2

li = []
for i in range(1, 11):
  li.append(i)

for i in li:
  print(i,end=" ")

557 : 배열1 - 자가진단3

li = input().split()

for i,a in enumerate(li):
  if i == 0 or i == 3 or i == 6:
    print(a, end=" ")

li = input().split()

for i in range(0, len(li)):
  if i == 0 or i == 3 or i == 6:
    print(li[i], end=" ")

558 : 배열1 - 자가진단4

li = list(map(int, input().split()))

for a in range(len(li)-2, -1, -1):
  print(li[a], end=" ")

li = list(map(int, input().split()))
li = li[:-1]
li.reverse()
print(li)

634 : 반복제어문3 - 자가진단2

a = int(input())

for i in range(1,a+1):
  for _ in range(0, i):
    print("*", end="")
  print()

547 : 반복제어문2 - 자가진단7

for i in range(2,7):
  for j in range(0,5):
    print(i + j, end = " ")
  print()

548 : 반복제어문2 - 자가진단8

for i in range(2,5):
  for j in range(1,6):
    print("%-2d * %2d = %3d  " %(i, j, i*j), end = " ")
  print()

133 : 반복제어문2 - 형성평가4

n = int(input())
cnt = 0
sum = 0
for _ in range(0,n):
  a = int(input())
  sum += a
  cnt += 1

print("%.2f" %(sum/cnt))

n = int(input())
li = list(map(int, input().split()))
cnt = 0
sum = 0
for a in li:
  sum += a
  cnt += 1

print("%.2f" %(sum/cnt))

137 : 반복제어문2 - 형성평가8

a,b = map(int, input().split())

for i in range(1, a+1):
  for j in range(1, b+1):
    print("%d" %(i*j), end = " ")
  print(" ");

138 : 반복제어문2 - 형성평가9

a = int(input())

for i in range(1, a + 1):
  for j in range(1, a + 1):
    print("(%d, %d)" %(i,j), end = " ")
  print()

139 : 반복제어문2 - 형성평가A

a, b = map(int, input().split())

for i in range(1, 10):
  for j in range(a, b-1, -1):
    print("%-2d * %2d = %2d" %(j, i, j*i), end = " ")
  print()