경우없는 개발 블로그

문제 상황

대략  로그아웃을 한뒤에

다시 메인페이지에서 리뷰페이지로 넘어가면 

지도등 리뷰가 전부 랜더링 되지 않는 문제 (스크린샷에서는 고친이후라 랜더링 되있음)

상황을 간단히 설명하자면, 사용자가 리뷰를 제출한 후 바로 로그아웃하고 다시 동일한 페이지를 방문할 때, 페이지의 일부만 렌더링되는 문제가 발생했습니다

그런데 이 문제 해결에 대해 보기 전에 CSRF 토큰에 대한 이해가 필요하니 CSRF 에대해 이해해보도록 합시다

CSRF란 무엇인가?

CSRF는 사용자가 신뢰하는 웹 애플리케이션에서 사용자도 모르게 공격자가 조작한 요청을 서버로 전송하게 하는 공격 방식입니다. 이 공격의 핵심은 사용자가 이미 인증된 상태에서 발생한다는 점입니다.

예시로 보는 CSRF 공격

사용자가 은행 웹사이트에 로그인한 상태에서, 공격자가 보낸 이메일이나 메시지에 포함된 링크를 클릭하면 사용자는 자신도 모르게 공격자가 설계한 악의적인 요청을 은행 서버에 보내게 됩니다. 예를 들어, 링크를 클릭함으로써 사용자의 계좌에서 공격자의 계좌로 돈이 이체될 수 있습니다.

이때 중요한 점은 공격자는 사용자의 세션을 악용하여 요청을 보낼 뿐, 서버의 응답 내용은 확인할 수 없다는 것입니다. 그럼에도 불구하고, 이 방식은 공격자가 사용자 권한으로 중요한 작업을 수행할 수 있기 때문에 매우 위험합니다.

CSRF 토큰이란?

CSRF 공격을 방지하기 위한 주요 방법 중 하나가 바로 CSRF 토큰을 사용하는 것입니다. CSRF 토큰은 웹 애플리케이션이 각 사용자 세션마다 고유하게 생성하는 임의의 난수입니다.

이 토큰은 사용자가 서버에 요청을 보낼 때마다 함께 전송되며, 서버는 이 토큰을 검증하여 요청이 실제로 해당 세션의 사용자에 의해 발생했는지를 확인합니다.

CSRF 토큰의 동작 원리

1. 토큰 발급: 사용자가 웹 애플리케이션에 접속하면, 서버는 사용자 세션에 고유한 CSRF 토큰을 생성하여 저장합니다.
2. 토큰 전달: 서버는 사용자에게 HTML 페이지를 전달할 때, 이 CSRF 토큰을 숨겨진 폼 필드(<input type="hidden">)에 포함시켜 클라이언트에게 전송합니다.
3.  
    

4. <input type="hidden" name="${_csrf.parameterName}" value="${_csrf.token}"/>

5. 요청 시 토큰 전송: 사용자가 폼을 제출하거나 서버로 요청을 보낼 때, 해당 요청에 이 숨겨진 필드의 CSRF 토큰이 포함되어 전송됩니다
6. 토큰 검증: 서버는 요청을 받을 때, 요청에 포함된 토큰과 세션에 저장된 토큰을 비교합니다. 두 토큰이 일치하면 요청을 처리하고, 그렇지 않으면 요청을 거부합니다

Spring Security, Thymeleaf 및 세션 관리 이슈 해결 방법

사전 지식

1. Spring Security의 세션 생성 전략:
   • 기본적으로 Spring Security는 "필요 시 생성" 전략을 사용합니다. 즉, 보안이 필요한 시점에 세션을 생성합니다.
2. Spring Session 생성 제한:
   • 세션은 response가 커밋되기 이전에만 생성될 수 있습니다. 즉, 응답이 반환된 후에는 세션을 새로 생성할 수 없습니다.
3. Spring Security의 폼 로그아웃 기능:
   • 기본적으로 서버 측 세션만 무효화되고 클라이언트의 쿠키 값에 있는 세션 ID는 그대로 유지됩니다. 이 세션 ID는 더 이상 유효하지 않은 세션을 참조하게 됩니다.
4. Thymeleaf의 렌더링 방식:
   • Thymeleaf는 Spring MVC와 함께 동작하며, 요청당 하나의 스레드에서 동기적으로 처리됩니다. 컨트롤러가 모든 로직을 처리한 후 Thymeleaf가 HTML을 렌더링합니다.
   • Thymeleaf는 메모리 최적화를 위해 기본적으로 8KB의 버퍼를 사용하여 렌더링된 HTML 파일을 CHUNKED 방식으로 나눠서 전송합니다. 버퍼가 가득 차면 전송을 시작하고, 남은 부분을 계속 렌더링합니다.
5. CSRF 보안 및 Thymeleaf와의 연동:
   • CSRF 보호를 위해 Spring Security와 Thymeleaf가 협력하여 자동으로 처리합니다.
     • Thymeleaf는 POST, PUT, DELETE 요청에 대한 폼 태그를 렌더링할 때 hidden 태그로 csrf_라는 이름의 태그를 추가합니다.
     • Spring Security는 CSRF 필터를 통해 클라이언트가 보유한 세션 ID에 매핑된 세션이 유효한지 확인하고, 유효하지 않거나 세션이 없을 경우 새로운 세션을 생성하여 CSRF 토큰을 부여합니다.
     • 클라이언트가 요청을 보낼 때 세션에 저장된 CSRF 토큰과 폼의 csrf_ 태그 값을 비교하여 유효성을 판단합니다.

문제 상황

환경

• 세션 생성 전략은 기본값인 "필요 시 생성".
• 로그인 방식은 폼 로그인 방식.

문제가 발생하는 조건

1. 로그아웃을 한 뒤, 음식점 세부 페이지에 접근.
2. 해당 페이지에는 댓글이 2개 이상 있어 데이터 양이 증가.

문제 증상

• 음식점 세부 페이지가 부분적으로 잘려서 클라이언트에 반환됩니다.
• 페이지를 다시 방문하더라도 문제가 반복되며, 다른 세부 페이지를 들린 후에는 정상 동작합니다.

이는 해당 페이지를 메인화면에서 재방문하더라도 반복해서 일어나며, 다른 아무 세부 음식점을 들렸다가 오면 정상작동합니다

문제 상황 분석

1. 로그아웃 후 클라이언트의 상태:
   • 로그아웃 후에도 클라이언트 측 쿠키에는 여전히 세션 ID가 남아 있지만, 해당 세션은 서버 측에서 무효화된 상태입니다. 즉, 더 이상 유효한 세션과 매핑되지 않습니다.
   • 음식점 세부 페이지에는 POST 요청을 보내는 폼이 있으며, 이로 인해 CSRF 토큰이 필요합니다.
   • Thymeleaf는 CSRF 토큰을 요청하지만, 클라이언트가 여전히 유효하지 않은 세션 ID를 서버에 전달하게 되어, 서버는 새로운 세션을 생성하고 CSRF 토큰을 부여합니다.
2. Thymeleaf의 CHUNKED 응답과 CSRF 문제:
   • 댓글이 2개 이상인 상황에서는 데이터 양이 증가하여 Thymeleaf가 CHUNKED 방식을 통해 HTML을 전송하게 됩니다.
   • Thymeleaf는 응답을 버퍼에 저장하고 8KB가 가득 차면 일부분을 전송한 후 남은 부분을 계속 렌더링합니다.
   • 그러나 세션은 응답이 커밋되기 전까지만 생성할 수 있습니다. 이미 CHUNKED로 일부 응답이 전송된 후, CSRF 토큰을 추가하기 위해 새로운 세션이 필요할 경우 세션을 생성할 수 없게 됩니다.
   • 이로 인해 페이지의 하단 부분이 제대로 렌더링되지 않고 잘린 상태로 클라이언트에 전달됩니다.
3. 다른 페이지를 방문하면 정상 동작하는 이유:
   • 문제를 겪은 후 다른 페이지를 방문하면 새로운 세션이 생성되어 CSRF 토큰이 정상적으로 부여됩니다. 이후 문제 있는 페이지에 다시 접근하면 CSRF 토큰을 재생성할 필요가 없으므로 정상 동작합니다.

해결책

1. 세션 생성 전략 변경:
   • 모든 요청에 대해 세션을 생성하도록 설정할 수 있습니다. 그러나 이는 메모리 소비가 늘어나 비효율적일 수 있습니다.
2. Thymeleaf 버퍼 크기 조정:
   • Thymeleaf의 기본 버퍼 크기인 8KB를 늘리거나 CHUNKED 방식을 사용하지 않도록 전체 파일을 한 번에 반환하도록 설정할 수 있습니다. 이 방법은 페이지 크기가 클 경우 메모리 사용량이 증가하므로 주의가 필요합니다.

   spring.thymeleaf.buffer-size=64KB

3. CSRF 토큰을 직접 처리:
   • CSRF 토큰을 직접 관리하거나 필터를 커스텀하여 CHUNKED 렌더링 과정에서 세션 문제를 방지할 수 있습니다.
   • 또한 Ajax를 활용하여 CSRF 토큰을 동적으로 받아오는 방식으로 처리할 수 있습니다.
4. Thymeleaf 커밋 시점 조정:
   • 문제의 원인이 타임리프의 응답 커밋 시점과 스프링 시큐리티의 동작 순서 충돌에서 비롯된 만큼, 해결 방법은 타임리프의 커밋 시점을 조정하는 것입니다.
   • 타임리프가 HTML을 처리하는 동안 부분적인 출력을 지연시키도록 설정을 변경하면, 이 문제가 해결됩니다.
   • 설정 파일에 아래 내용을 추가하여 타임리프가 전체 HTML을 처리할 때까지 응답을 커밋하지 않도록 설정할 수 있습니다:

   # Thymeleaf 설정 spring.thymeleaf.servlet.produce-partial-output-while-processing=false

    
   이 설정을 통해 타임리프는 전체 HTML이 처리될 때까지 응답을 커밋하지 않게 되며, 스프링 시큐리티가 CSRF 토큰을 폼에 추가할 수 있는 시간을 확보하게 됩니

냠톨릭은?

현재 운영측에서 사용자를 차단 하기위한 세션 전략 변경과 위의 해결책 적용으로 인해 1, 4번 해결책이 모두 적용되어 있다.
또한 거의 첫번째로 버퍼에 들어가는게 거의 확실한 nav bar에서 meta csrf 태그를 발견했는데 이에 의해 3번도 적용되어 있다

결론

이 문제는 Spring Security와 Thymeleaf의 세션 및 CSRF 처리 과정에서 발생하는 특수한 케이스입니다. 클라이언트는 세션 자체를 가지고 있지 않고, 단지 세션 ID를 쿠키로 보유하며, 로그아웃 후에도 이 세션 ID는 남아 있을 수 있지만 서버에서 더 이상 유효하지 않다는 점을 유념해야 합니다. 이를 해결하기 위해 세션 생성 전략을 조정하거나 Thymeleaf의 버퍼 크기를 조절하는 등의 해결책을 사용할 수 있습니다.

이러한 구조적 문제는 보통 예측하기 어려운 부분이니, 실무에서는 항상 페이지 성능과 메모리 최적화를 함께 고려하는 것이 중요합니다.

#문제 간단 정리

#문제 해결 방법

우선순위 큐를 써도 되지만

n이 작기때문에

나이브하게 그냥 구현해도 돌아간다

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

    vector<int> times(c);
    for (int i = 0; i < c; i++) {
        cin >> times[i];
    }

    vector<int> cashier(n, 0);  // 각 계산대의 남은 시간
    vector<int> ans(c);  // 각 고객이 배정된 계산대 번호를 저장

    for (int i = 0; i < c; i++) {
        // 가장 빨리 비는 계산대를 찾기
        int min_time = cashier[0];
        int min_index = 0;

        for (int j = 1; j < n; j++) {
            if (cashier[j] < min_time) {
                min_time = cashier[j];
                min_index = j;
            }
        }

        // 고객을 가장 빨리 비는 계산대에 배치
        ans[i] = min_index + 1;
        cashier[min_index] += times[i];  // 해당 계산대의 남은 시간 갱신
    }

    // 결과 출력
    for (int a : ans) {
        cout << a << " ";
    }

    return 0;
}

https://www.acmicpc.net/problem/30617

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    int l_prev = 0, r_prev = 0;
    int l, r;
    int fun_score = 0;

    for (int i = 0; i < T; i++) {

        cin >> l >> r;

        if (i > 0) {
            // 재미도 계산
            if (l != 0 && l == l_prev) {
                fun_score++;
            }
            if (r != 0 && r == r_prev) {
                fun_score++;
            }

        }
        if (r != 0 && l == r) {
            fun_score++;
        }

        // 현재 상태를 이전 상태로 업데이트
        l_prev = l;
        r_prev = r;
    }

    cout << fun_score << endl;
    return 0;
}

https://www.acmicpc.net/problem/16464

#문제 간단 정리

수학 문제이다

#문제 해결 방법

일단 n (n+1) 로 나눠지면 n-1 n n+1 로 해결이 가능한데

불가능한 경우는 2의 거듭제곱으로 구성되는 경우밖에 없다

2의 거듭제곱은 완벽한 대칭이기때문에 n n+1 로 분할 할 수 가없다

즉 2의 거듭제곱인지만 확인해주면 된다

#전체 코드

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        bool canWin = false;
        while (N != 1) {
            if (N % 2 == 1) {
                canWin = true;
                break;
            }
            N /= 2;
        }
        if (canWin) {
            cout << "Gazua" << endl;
        } else {
            cout << "GoHanGang" << endl;
        }
    }
    return 0;
}

https://www.acmicpc.net/problem/18243

#문제 간단 정리

플로이드 워셜을 사용하자

#문제 해결 방법

모든 간선에서에 간선까지의 거리를 찾아야되니까 플로이드 워셜을 사용하자

그런데 n 이 작으므로 n^2 이상을 사용하는 bfs 를 사용해도 된다.

플로이드 워셜 코드

https://dfdfg42.tistory.com/entry/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-C%EC%BD%94%EB%93%9C

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

void floydWarshall(vector<vector<int>>& dist, int N) {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<vector<int>> dist(N, vector<int>(N, INF));

    // 자기 자신으로의 거리는 0으로 초기화
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < K; i++) {
        int A, B;
        cin >> A >> B;
        A--; // 0-based index
        B--; // 0-based index
        dist[A][B] = 1;
        dist[B][A] = 1;
    }

    floydWarshall(dist, N);

    bool flag = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dist[i][j] > 6) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
    }

    if (flag) {
        cout << "Small World!" << '\n';
    }
    else {
        cout << "Big World!" << '\n';
    }

    return 0;
}

LIS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int LIS(const vector<int>& arr) {
    if (arr.empty()) return 0;

    vector<int> lis;
    
    for (int i = 0; i < arr.size(); ++i) {
        auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (it == lis.end()) {
            lis.push_back(arr[i]);
        } else {
            *it = arr[i];
        }
    }

    return lis.size();
}

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << "LIS의 길이: " << LIS(arr) << endl;
    return 0;
}

LCS

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int LCS(const string& X, const string& Y) {
    int m = X.size();
    int k = Y.size();
    vector<vector<int>> lcs(m + 1, vector<int>(k + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }

    return lcs[m][k];
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCAB";
    cout << "LCS의 길이: " << LCS(X, Y) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm> // std::min 사용

using namespace std; // std 네임스페이스를 전역적으로 사용

const int INF = 1e9; // 무한대를 의미하는 큰 값

void floydWarshall(vector<vector<int>>& dist, int V) {
    // 모든 정점 쌍 (i, j)에 대해 i에서 j로의 최단 경로 계산
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][k] < INF && dist[k][j] < INF) { // 두 값이 모두 유효한 경우에만 갱신
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    int V; // 정점의 개수
    cout << "정점의 개수를 입력하세요: ";
    cin >> V;

    // 거리 행렬 초기화
    vector<vector<int>> dist(V, vector<int>(V));

    cout << "거리 행렬을 입력하세요 (직접 연결되지 않은 경우 " << INF << "을 입력하세요):\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cin >> dist[i][j];
        }
    }

    // 플로이드-워셜 알고리즘 수행
    floydWarshall(dist, V);

    // 결과 출력
    cout << "최단 거리 행렬:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

https://www.acmicpc.net/problem/19554

#include <iostream>
using namespace std;

int main() {
    long long N;
    cin >> N;

    long long left = 1, right = N;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        cout << "? " << mid << endl;

        int response;
        cin >> response;

        if (response == 0) {
            cout << "= " << mid << endl;
            break;
        }
        else if (response == -1) {
            left = mid + 1;
        }
        else if (response == 1) {
            right = mid - 1;
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/17610

#문제 간단 정리

#문제 해결 방법

생각보다 무게를 만들수 있는 가짓수가 많지 않기때문에

우선 그릇 하나만 써서 만들수 있는 무게를 모두 만든다.

그 이후에 만든 무게중에 두개를 빼서 만들수 있는 무게를 확인한다.

이 모든 만든 무게들을 출력해주면 된다.

나는 무게 만드는데는 dfs를 사용했다.

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>


using namespace std;

vector<int> mess;
vector<int> makes;
vector<bool> check;
vector<bool> dfsCheck;
vector<int> messNext;

//한곳에 만들수 있는 모든 무게추 구하기
void dfs(int index,int sumMess) {

    for (int i = 0; i < mess.size(); i++) {
        if (dfsCheck[i] == false) {
            dfsCheck[i] = true;
            if (check[sumMess + mess[i]] == false) {
                check[sumMess + mess[i]] = true;
                messNext.push_back(sumMess + mess[i]);
                dfs(i,sumMess + mess[i]);
            }
            dfsCheck[i] = false;
        }
    }

}


int main()
{
    int k;
    cin >> k;
    int s = 0;
    mess.resize(k);
    check.resize(3000'001, false);
    dfsCheck.resize(3000'001, false);

    for (int i = 0; i < k; i++) {
        cin >> mess[i];
        s += mess[i];
        //cout << "s: " << s << '\n';
        messNext.push_back(mess[i]);
        check[mess[i]] = true;
    }

    for (int i = 0; i<mess.size(); i++) {
        dfsCheck[i] = true;
        dfs(i, mess[i]);

    }

    //두개 골라서 빼기
    for (int i = 0; i < messNext.size()-1; i++) {
        for (int j = i + 1; j < messNext.size(); j++) {
            if (check[abs(messNext[i] - messNext[j])] == false) {
                check[abs(messNext[i] - messNext[j])] = true;
            }
        }

    }

    ////무게확인
    //for (int i = 0; i <= s; i++) {
    //    if (check[i] == true) {
    //        cout << i << " ";
    //    }
    //}

    //안 만들어진 무게추 확인
    int count = 0;
    //cout << "count: ";
    for (int i = 1; i <= s; i++) {
        if (check[i] == false) {
            count++;
        }
    }
    cout << count << '\n';

}

https://www.acmicpc.net/problem/20209

#문제 간단 정리

브루트포스 완전탐색을 활용하자

bfs 를 활용하면 된다

#문제 해결 방법

일단 문제가 좀 설명이 길기 때문에 이해하기 좀 걸릴 수가 있다.

우선 이 문제에서 주목해야 될 포인트는 4가 넘어가면 5로 나눈 값으로 큐브값을 유지한다는것이다.

그렇다면 우리는 스위치의 개수도 8개로 가짓수가 적고

계속해서 5로 나눈다면 같은 상태가 반복된다는 걸 알 수 있다.

이부분에서 전체 가짓수가 적다는걸 파악한다

여기서 같은 스위치를 대략 최대 4번정도 누른다면 원래 상태로 되돌아 올 수 있다는 걸 관찰 할 수 있고

각 스위치 하나마다 최대 5가지의 상태가 파생되니까

5^k 가 총 가짓수인걸 파악할 수 있다.

그렇다면 중복상태를 뛰어넘어서 완전탐색을 하면 되겟다는 생각이 든다. (가짓수가 적으니까)

-> 여기서 중복 제거를 위해서 맵이나 셋으로 중복 상태를 관리하고

-> 완전탐색은 최소 거리를 찾아야되기 때문에 bfs 가 적절하다는 생각이 든다.

그렇다면 이제 구현할 차례,

유의할점은 애초에 주어진 상태가 전부 같은 숫자로 주어진 

정답 상태로 초기에 주어질 수 있음만 유의하도록 하자.

자세한 구현은 코드보고 이해하도록 하자

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

// 모든 큐브의 숫자가 동일한지 확인하는 함수
bool equal(vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] != vec[0]) {
            return false;
        }
    }
    return true;
}

int main() {
    
    int n, k;
    cin >> n >> k;
    
    vector<int> cubes;
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        cubes.push_back(input);
    }
    
    vector<vector<int>> switches(k);
    for (int i = 0; i < k; i++) {
        int input;
        cin >> input;

        for (int j = 0; j < input; j++) {
            int input2; cin >> input2;
            switches[i].push_back(input2-1);
        }

    }

    set<vector<int>> cubeSet;


    //큐브상태,횟수
    queue<pair<vector<int>,int>> q;
    q.push({ cubes,0 });
    cubeSet.insert(cubes);

    while (!q.empty()) {

        vector<int> front = q.front().first;
        int seq = q.front().second;
        q.pop();
        if (equal(front)) {
            cout << seq  << '\n';
            return 0;
        }
         
        for (int i = 0; i < k; i++) {
            vector<int> next = front;
            for (auto a : switches[i]) {
                next[a] += i+1;
                if (next[a] > 4) {
                    next[a] %= 5;
                }
            }
            if (cubeSet.find(next) == cubeSet.end()) {
                cubeSet.insert(next);
                q.push({ next,seq + 1 });
            }

        }

    }

    cout << -1 << '\n';
    

    return 0;
}

//주석달린 버전

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

// 모든 큐브의 숫자가 동일한지 확인하는 함수
bool equal(vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] != vec[0]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> cubes(n);
    for (int i = 0; i < n; i++) {
        cin >> cubes[i];
    }
    
    vector<vector<int>> switches(k);
    for (int i = 0; i < k; i++) {
        int m;
        cin >> m;
        switches[i].resize(m);
        for (int j = 0; j < m; j++) {
            cin >> switches[i][j];
            switches[i][j]--; // 1-based index를 0-based index로 변환
        }
    }

    // 중복 상태 관리를 위한 set
    set<vector<int>> visited;

    // 큐브 상태와 스위치를 누른 횟수를 저장할 큐
    queue<pair<vector<int>, int>> q;
    q.push({cubes, 0});
    visited.insert(cubes);

    while (!q.empty()) {
        vector<int> current = q.front().first;
        int moves = q.front().second;
        q.pop();

        // 모든 큐브의 숫자가 동일하면 정답 출력 후 종료
        if (equal(current)) {
            cout << moves << endl;
            return 0;
        }

        // 각 스위치를 한번씩 눌러보는 과정
        for (int i = 0; i < k; i++) {
            vector<int> next = current;
            for (int idx : switches[i]) {
                next[idx] = (next[idx] + (i + 1)) % 5; // 스위치에 따라 숫자 변경
            }

            // 이미 방문한 상태가 아니면 큐와 set에 추가
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push({next, moves + 1});
            }
        }
    }

    // 모든 경우를 탐색했음에도 정답을 찾지 못한 경우
    cout << -1 << endl;
    return 0;
}