Trong lĩnh vực xử lý video và phân tích chuyển động, việc xác định các mẫu chuyển động lặp lại là rất quan trọng. Một tác vụ phổ biến là tìm kiếm "chuyển động đặc trưng" dài nhất, tức là một đặc trưng (được biểu diễn dưới dạng tọa độ 2D, ví dụ: <x, y>) xuất hiện liên tục qua nhiều khung hình. Nếu hai đặc trưng giống hệt nhau (cùng tọa độ x và y), chúng được coi là cùng một loại đặc trưng. Khi một đặc trưng nhất quán trong nhiều khung hình liên tiếp, nó tạo thành một "chuyển động đặc trưng".

Ví dụ, nếu đặc trưng <a, b> xuất hiện ở các khung hình 2, 3, 4 và sau đó lại xuất hiện ở khung hình 7, 8, thì nó tạo ra hai chuỗi chuyển động đặc trưng riêng biệt: một chuỗi kéo dài từ khung hình 2 đến 4 (độ dài 3) và một chuỗi khác từ khung hình 7 đến 8 (độ dài 2). Mục tiêu là tìm ra chuỗi có độ dài lớn nhất trong toàn bộ video, cho dù đặc trưng đó là gì.

Dữ liệu đầu vào bao gồm thông tin về các đặc trưng có trong mỗi khung hình của video. Số lượng đặc trưng có thể thay đổi giữa các khung hình.

Mô tả đầu vào:

Đầu tiên là một số nguyên dương N, biểu thị số lượng bộ dữ liệu thử nghiệm.

Đối với mỗi bộ dữ liệu thử nghiệm:

• Dòng đầu tiên chứa một số nguyên dương M, đại diện cho tổng số khung hình trong video.
• M dòng tiếp theo mô tả từng khung hình:
  • Số đầu tiên trên mỗi dòng là số lượng đặc trưng trong khung hình đó.
  • Các cặp số tiếp theo là giá trị tọa độ (x, y) của mỗi đặc trưng. Ví dụ, dòng thứ ba của ví dụ đầu vào cho biết có hai đặc trưng: <1, 1> và <2, 2>.

Tổng số lượng đặc trưng trên tất cả các khung hình trong tất cả các bộ dữ liệu không vượt quá 100.000.

Các ràng buộc về giá trị: 1 ≤ N ≤ 100.000, 1 ≤ M ≤ 10.000, số đặc trưng mỗi khung hình ≤ 10.000. Giá trị tọa độ của đặc trưng là các số nguyên không âm.

Mô tả đầu ra:

Đối với mỗi bộ dữ liệu thử nghiệm, in ra độ dài của chuỗi chuyển động đặc trưng dài nhất tìm được trên một dòng.

Ví dụ đầu vào 1:

1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1

Ví dụ đầu ra 1:

3

Giải thích ví dụ 1:

Đặc trưng <1, 1> xuất hiện liên tục trong 3 khung hình (khung hình 1, 2, 3). Đây là chuỗi liên tục dài nhất so với bất kỳ đặc trưng nào khác, do đó kết quả là 3.

Đây là một bài toán logic kinh doanh, độ khó không cao.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numTestCases = scanner.nextInt();
        while (numTestCases-- > 0) {
            int numFrames = scanner.nextInt();

            // Stores the maximum consecutive count for each feature
            Map maxConsecutiveCounts = new HashMap<>();
            // Stores the current consecutive count for each feature in the ongoing sequence
            Map currentConsecutiveCounts = new HashMap<>();
            // Stores features present in the previous frame
            Set<String> previousFrameFeatures = new HashSet<>();
            // Stores features present in the current frame being processed
            Set<String> currentFrameFeatures = new HashSet<>();

            for (int frameIndex = 0; frameIndex < numFrames; frameIndex++) {
                int numFeaturesInFrame = scanner.nextInt();
                currentFrameFeatures.clear(); // Clear features from the last frame

                for (int featureCount = 0; featureCount < numFeaturesInFrame; featureCount++) {
                    int xCoord = scanner.nextInt();
                    int yCoord = scanner.nextInt();
                    String featureKey = xCoord + "_" + yCoord;

                    currentFrameFeatures.add(featureKey); // Add to current frame's features

                    // Initialize or update counts for this feature
                    if (!maxConsecutiveCounts.containsKey(featureKey)) {
                        maxConsecutiveCounts.put(featureKey, 1);
                        currentConsecutiveCounts.put(featureKey, 1);
                    } else {
                        // Check if this feature was present in the previous frame
                        if (previousFrameFeatures.contains(featureKey)) {
                            int currentCount = currentConsecutiveCounts.get(featureKey) + 1;
                            currentConsecutiveCounts.put(featureKey, currentCount);

                            // Update max count if current sequence is longer
                            if (maxConsecutiveCounts.get(featureKey) < currentCount) {
                                maxConsecutiveCounts.put(featureKey, currentCount);
                            }
                        } else {
                            // Feature appeared after a gap, reset current count to 1
                            currentConsecutiveCounts.put(featureKey, 1);
                        }
                    }
                }

                // Prepare for the next frame: current frame becomes the previous frame
                previousFrameFeatures.clear();
                previousFrameFeatures.addAll(currentFrameFeatures);
            }

            // Find the overall maximum length from all features
            int overallMaxLength = 0;
            if (!maxConsecutiveCounts.isEmpty()) {
                overallMaxLength = Collections.max(maxConsecutiveCounts.values());
            }

            System.out.println(overallMaxLength);
        }
        scanner.close();
    }
}